Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal Mending
243
0
0.0
(
0
)
Added by
Darya Melnyk
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to patch a hole. We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $Pi$ can be solved in $O(log^* n)$, there is always a restriction $Pi subseteq Pi$ that is still efficiently solvable but that is also $O(1)$-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $Theta(log n)$, or $Theta(n)$, while in general graphs the structure is much more diverse.
rate research
Read More
Determining the space complexity of $x$-obstruction-free $k$-set agreement for $xleq k$ is an open problem. In $x$-obstruction-free protocols, processes are required to return in executions where at most $x$ processes take steps. The best known upper bound on the number of registers needed to solve this problem among $n>k$ processes is $n-k+x$ registers. No general lower bound better than $2$ was known. We prove that any $x$-obstruction-free protocol solving $k$-set agreement among $n>k$ processes uses at least $lfloor(n-x)/(k+1-x)rfloor+1$ registers. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic wait-free $k$-set agreement: if a protocol uses fewer registers, then it is possible for $k+1$ processes to simulate the protocol and deterministically solve $k$-set agreement in a wait-free manner, which is impossible. A critical component of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce a new augmented snapshot object, which facilitates this. We also prove that any space lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo termination. Hence, our lower bound of $lfloor(n-1)/krfloor+1$ for the obstruction-free ($x=1$) case also holds for randomized wait-free free protocols. In particular, this gives a tight lower bound of exactly $n$ registers for solving obstruction-free and randomized wait-free consensus. Finally, our new techniques can be applied to get a space lower of $lfloor n/2rfloor+1$ for $epsilon$-approximate agreement, for sufficiently small $epsilon$. It requires participating processes to return values within $epsilon$ of each other. The best known upper bounds are $lceillog(1/epsilon)rceil$ and $n$, while no general lower bounds were known.
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $Theta(log^* n)$, or $Theta(n)$, and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $Theta(log^* n)$, and $Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $Theta(log^* n)$ or $Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $Theta(log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A circ S_k$, where $A$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an $n$-qubit product state $|vrangle$ with mean energy $e_0=langle v|H|vrangle$ and variance $mathrm{Var}=langle v|(H-e_0)^2|vrangle$, and outputs a state with an energy that is lower than $e_0$ by an amount proportional to $mathrm{Var}^2/n$. In a typical case, we have $mathrm{Var}=Omega(n)$ and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to $k$-local Hamiltonians and entangled initial states.
We show that any randomised Monte Carlo distributed algorithm for the Lovasz local lemma requires $Omega(log log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where $d$ is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovasz local lemma with a running time of $O(log n)$ rounds in bounded-degree graphs, and the best lower bound before our work was $Omega(log^* n)$ rounds [Chung et al. 2014].
We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
