Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKarchmer-Wigderson Games for Hazard-free Computation
56
0
0.0
(
0
)
Added by
Balagopal Komarath
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth $2$ that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a significant step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.
rate research
Read More
Given a family of graphs $mathcal{F}$, we define the $mathcal{F}$-saturation game as follows. Two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph in $mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $textrm{sat}_g(n,mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally. In general there are very few non-trivial bounds on the order of magnitude of $textrm{sat}_g(n,mathcal{F})$. In this work, we find collections of infinite families of cycles $mathcal{C}$ such that $textrm{sat}_g(n,mathcal{C})$ has linear growth rate.
We give a new algorithm for Unique Games which is based on purely {em spectral} techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the {em Label-Extended} graph associated with the instance of Unique Games. We further show that on input the integrality gap instance of Khot and Vishnoi, our algorithm runs in quasi-polynomial time and decides that the instance if highly unsatisfiable. Notably, when run on this instance, the standard SDP relaxation of Unique Games {em fails}. As a special case, we also re-derive a polynomial time algorithm for Unique Games on expander constraint graphs. The main ingredient of our algorithm is a technique to effectively use the full spectrum of the underlying graph instead of just the second eigenvalue, which is of independent interest. The question of how to take advantage of the full spectrum of a graph in the design of algorithms has been often studied, but no significant progress was made prior to this work.
We investigate the value of parallel repetition of one-round games with any number of players $kge 2$. It has been an open question whether an analogue of Razs Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.
In this thesis we introduce quantum refereed games, which are quantum interactive proof systems with two competing provers. We focus on a restriction of this model that we call short quantum games and we prove an upper bound and a lower bound on the expressive power of these games. For the lower bound, we prove that every language having an ordinary quantum interactive proof system also has a short quantum game. An important part of this proof is the establishment of a quantum measurement that reliably distinguishes between quantum states chosen from disjoint convex sets. For the upper bound, we show that certain types of quantum refereed games, including short quantum games, are decidable in deterministic exponential time by supplying a separation oracle for use with the ellipsoid method for convex feasibility.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
