1. 
 Austrin, Per, et al.
(författare)

Inapproximability of Treewidth, OneShot Pebbling, and Related Layout Problems
 2012

Ingår i: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).  Berlin, Heidelberg : Springer Berlin Heidelberg. ; , s. 1324

Konferensbidrag (refereegranskat)abstract
 We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, oneshot black (and blackwhite) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as minimum cut linear arrangement and interval graph completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are hard to approximate within any constant factor.


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

Automating algebraic proof systems is NPhard
 2021

Ingår i: STOC 2021  Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.  New York, NY, USA : ACM.  07378017.  9781450380539 ; , s. 209222

Konferensbidrag (refereegranskat)abstract
 We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NPhard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or SheraliAdams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.


3. 
 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.  9781728196213  9781728196220 ; 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.


4. 
 de Rezende, Susanna F., 1989, et al.
(författare)

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Annan publikation (övrigt vetenskapligt/konstnärligt)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 two 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 subpolynomialline 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.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.


5. 
 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.


6. 
 Rezende, Susanna F.de, et al.
(författare)

KRW Composition Theorems via Lifting
 2024

Ingår i: Computational Complexity.  10163328. ; 33:1

Tidskriftsartikel (refereegranskat)abstract
 One of the major open problems in complexity theory is proving superlogarithmiclower bounds on the depth of circuits (i.e., P⊈NC1). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC1.Several works have made progress toward resolving this conjectureby proving special cases. In particular, these works proved the KRWconjecture for every outer function f, but only for few innerfunctions g. Thus, it is an important challenge to prove the KRWconjecture for a wider range of inner functions.In this work, we extend significantly the range of inner functionsthat can be handled. First, we consider the monotone versionof the KRW conjecture. We prove it for every monotone inner function gwhose depth complexity can be lowerbounded via a querytocommunicationlifting theorem. This allows us to handle several new and wellstudiedfunctions 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, whichcombines the nonmonotone complexity of the outer function f withthe monotone complexity of the inner function g. In this setting,we prove the KRW conjecture for a similar selection of inner functions g,but only for a specific choice of the outer function f.


7. 
 Wu, Yu, et al.
(författare)

Inapproximability of treewidth and related problems
 2015

Ingår i: IJCAI International Joint Conference on Artificial Intelligence.  : International Joint Conferences on Artificial Intelligence.  9781577357384 ; , s. 42224228

Konferensbidrag (refereegranskat)abstract
 Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum FillIn, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement. We show that, assuming Small Set Expansion Conjecture, all of these problems are NPhard to approximate to within any constant factor in polynomial time.

