1. 
 De Rezende, Susanna F., et al.
(författare)

KRW composition theorems via lifting
 2020

Ingår i: Proceedings  2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020.  02725428.  9781728196220  9781728196213 ; 2020November, s. 4349

Konferensbidrag (refereegranskat)abstract
 One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., mathrm{P} nsubseteq text{NC}{1}). Karchmer, Raz, and Wigderson [13] suggested to approach this problem by proving that depth complexity behaves'as expected' with respect to the composition of functions f diamond g. They showed that the validity of this conjecture would imply that mathrm{P} nsubseteq text{NC}{1}. Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function, but only for few inner functions. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function whose depth complexity can be lower bounded via a querytocommunication lifting theorem. This allows us to handle several new and wellstudied functions such as the stconnectivity, clique, and generation functions. In order to carry this progress back to the nonmonotone setting, we introduce a new notion of semimonotone composition, which combines the nonmonotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function f.


2. 
 De Rezende, Susanna, et al.
(författare)

Lifting with simple gadgets and applications to circuit and proof complexity
 2020

Ingår i: Proceedings  2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020.  02725428.  9781728196213  9781728196220 ; 2020November, s. 2430

Konferensbidrag (refereegranskat)abstract
 We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greaterthan. We apply our generalized theorem to solve three open problems: •We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude. •We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a nonexplicit separation was known. •We give the strongest separation todate between monotone Boolean formulas and monotone Boolean circuits. Namely, we show that the classical GEN problem, which has polynomialsize monotone Boolean circuits, requires monotone Boolean formulas of size 2{Omega(n text{polylog}(n))}. An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal. This is an extended abstract. The full version of the paper is available at https://arxiv.org/abs/2001.02144.


3. 
 Björklund, Andreas, et al.
(författare)

Computing the Tutte polynomial in vertexexponential time
 2008

Ingår i: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science.  02725428. ; , s. 677686

Konferensbidrag (refereegranskat)abstract
 The deletioncontraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and FortuinKasteleyn in statistical physics. Prior to this work, deletioncontraction was also the fastest known generalpurpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomialand hence, all the aforementioned invariants and moreof an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomialspace variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.


4. 
 Björklund, Andreas
(författare)

Determinant sums for undirected Hamiltonicity
 2010

Ingår i: 2010 IEEE 51st Annual Symposium On Foundations Of Computer Science.  02725428.  9780769542447 ; , s. 173182

Konferensbidrag (refereegranskat)abstract
 Abstract in UndeterminedWe present a Monte Carlo algorithm for Hamiltonicity detection in an nvertex undirected graph running in O*(1.657(n)) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the O*(2(n)) bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NPhard problems.For bipartite graphs, we improve the bound to O*(1.414(n)) time. Both the bipartite and the general algorithm can be implemented to use space polynomial in n.We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for kPath (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers (Bjorklund STACS 2010) to evaluate it.


5. 
 Björklund, Andreas, et al.
(författare)

The Parity of Directed Hamiltonian Cycles
 2013

Ingår i: Annual IEEE Symposium on Foundations of Computer Science.  02725428. ; , s. 727735

Konferensbidrag (refereegranskat)abstract
 We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.


6. 
 Conneryd, Jonas, et al.
(författare)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
 2023

Ingår i: Proceedings  2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023.  02725428.  9798350318944 ; , s. 111

Konferensbidrag (refereegranskat)abstract
 We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse ErdősRényi random graphs, are 3colourable.


7. 
 De Rezende, Susanna F., et al.
(författare)

Clique Is Hard on Average for Unary SheraliAdams
 2023

Ingår i: Proceedings  2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023.  02725428.  9798350318944 ; , s. 1225

Konferensbidrag (refereegranskat)abstract
 We prove that unary SheraliAdams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)clique in ErdősRényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudocalibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.


8. 
 Isaksson, Marcus, 1978, et al.
(författare)

The geometry of manipulation  A quantitative proof of the gibbard satterthwaite theorem
 2010

Ingår i: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010; Las Vegas, NV; 23 October 2010 through 26 October 2010.  02725428.  9780769542447 ; :Article number 5671191, s. 319328

Konferensbidrag (refereegranskat)abstract
 We prove a quantitative version of the GibbardSatterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of q >= 4 alternatives and n voters will be manipulable with probability at least 10(4)epsilon(2)n(3)q(30), where epsilon is the minimal statistical distance between f and the family of dictator functions. Our results extend those of [1], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [2], [3], [4], [5], [6]) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.

