kth.sePublications
Change search
Refine search result
12 1 - 50 of 56
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Alwen, Joël
    et al.
    de Rezende, Susanna F.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Cumulative Space in Black-White Pebbling and Resolution2017In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017Conference paper (Refereed)
    Abstract [en]

    We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.

  • 2. Atserias, A.
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow proofs may be maximally long2014In: Proceedings of the Annual IEEE Conference on Computational Complexity, 2014, p. 286-297Conference paper (Refereed)
    Abstract [en]

    We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size nω(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size nO(ω) is essentially tight. Moreover, our lower bounds can be generalized to polynomial calculus resolution (PCR) and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. Our results do not extend all the way to Lasserre, however-the formulas we study have Lasserre proofs of constant rank and size polynomial in both n and w.

  • 3.
    Atserias, Albert
    et al.
    Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..
    Bonacina, Ilario
    Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..
    de Rezende, Susanna F.
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Lauria, Massimo
    Sapienza Univ Roma, Dept Stat Sci, Rome, Italy..
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Razborov, Alexander
    Univ Chicago, Chicago, IL 60637 USA.;Steklov Math Inst, Moscow, Russia..
    Clique Is Hard on Average for Regular Resolution2018In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 866-877Conference paper (Refereed)
    Abstract [en]

    We prove that for k << (4)root n regular resolution requires length n(Omega(k)) to establish that an Erdos Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n(Omega(k)) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

  • 4. Atserias, Albert
    et al.
    Lauria, Massimo
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow Proofs May Be Maximally Long2016In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 17, no 3, article id 19Article in journal (Refereed)
    Abstract [en]

    We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n(Omega(w)). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n(O(w)) is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w.

  • 5. Beck, C.
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Tang, B.
    Some trade-off results for polynomial calculus2013In: STOC '13 Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, Association for Computing Machinery (ACM), 2013, p. 813-822Conference paper (Refereed)
    Abstract [en]

    We present size-space trade-offs for the polynomial calculus (PC) and polynomial calculus resolution (PCR) proof systems. These are the first true size-space trade-offs in any algebraic proof system, showing that size and space cannot be simultaneously optimized in these models. We achieve this by extending essentially all known size-space trade-offs for resolution to PC and PCR. As such, our results cover space complexity from constant all the way up to exponential and yield mostly superpolynomial or even exponential size blow-ups. Since the upper bounds in our trade-offs hold for resolution, our work shows that there are formulas for which adding algebraic reasoning on top of resolution does not improve the trade-off properties in any significant way. As byproducts of our analysis, we also obtain trade-offs between space and degree in PC and PCR exactly matching analogous results for space versus width in resolution, and strengthen the resolution trade-offs in [Beame, Beck, and Impagliazzo '12] to apply also to k-CNF formulas.

  • 6. Ben-Sasson, Eli
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A Space Hierarchy for k-DNF Resolution2009In: Electronic Colloquium on Computational Complexity, ISSN 1433-8092, Vol. 16Article in journal (Refereed)
  • 7. Ben-Sasson, Eli
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Short proofs may be spacious: An optimal separation of space and length in resolution2008In: Proc. Annu. IEEE Symp. Found. Comput. Sci. FOCS, 2008, p. 709-718Conference paper (Refereed)
    Abstract [en]

    A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space. In this paper we resolve the question by answering it negatively in the strongest possible way. We show that there are families of 6-CNF formulas of size n, for arbitrarily large n, that have resolution proofs of length O(n) but for which any proof requires space Ω(n/log n). This is the strongest asymptotic separation possible since any proof of length O(n) can always be transformed into a proof in space O(n/log n). Our result follows by reducing the space complexity of so called pebbling formulas over a directed acyclic graph to the black-white pebbling price of the graph. The proof is somewhat simpler than previous results (in particular, those reported in [Nordström 2006, Nordström and Håstad 2008]) as it uses a slightly different flavor of pebbling formulas which allows for a rather straightforward reduction of proof space to standard black-white pebbling price.

  • 8. Ben-Sasson, Eli
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs2009In: Electronic Colloquium on Computational Complexity, ISSN 1433-8092, Vol. 16Article in journal (Refereed)
  • 9. Berkholz, C.
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Supercritical space-width trade-offs for resolution2016In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)
    Abstract [en]

    We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width resolution proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben- Sasson 2009], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov 2016]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordström 2008].

  • 10. Berkholz, Christoph
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps2016In: PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), Institute of Electrical and Electronics Engineers (IEEE), 2016, p. 267-276Conference paper (Refereed)
    Abstract [en]

    We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n(Omega(k/logk)). Our trade-offs also apply to first-order counting logic, and by the known connection to the k-dimensional Weisfeiler-Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov ' 16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the quantifier depth required to distinguish them.

  • 11. Berkholz, Christoph
    et al.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Supercritical space-width trade-offs for resolution2020In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 49, no 1, p. 98-118Article in journal (Refereed)
    Abstract [en]

    We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [E. Ben-Sasson, SIAM J. Comput., 38 (2009), pp. 2511-2525], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [A.A. Razborov, J. ACM, 63 (2016), 16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [E. Ben-Sasson and J. Nordström, Short proofs may be spacious: An optimal separation of space and length in resolution, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 2008, pp. 709-718].

  • 12. Bhatttacharyya, Arnab
    et al.
    Grigorescu, Elena
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the Semantics of Local Characterizations for Linear-Invariant Properties2011Article in journal (Other academic)
    Abstract [en]

    A property of functions on a vector space is said to be linear-invariant if it is closed under linear transformations of the domain. Linear-invariant properties are some of the most well-studied properties in the field of property testing. Testable linear-invariant properties can always be characterized by socalled local constraints, and of late there has been a rapidly developing body of research investigating the testability of linear-invariant properties in terms of their descriptions using such local constraints. One problematic aspect that has been largely ignored in this line of research, however, is that syntactically distinct local characterizations need not at all correspond to semantically distinct properties. In fact, there are known fairly dramatic examples where seemingly infinite families of properties collapse into a small finite set that was already well-understood. In this work, we therefore initiate a systematic study of the semantics of local characterizations of linear-invariant properties. For such properties the local characterizations have an especially nice structure in terms of forbidden patterns on linearly dependent sets of vectors, which can be encoded formally as matroid constraints. We develop techniques for determining, given two such matroid constraints, whether these constraints encode identical or distinct properties, and show for a fairly broad class of properties that these techniques provide necessary and sufficient conditions for deciding between the two cases. We use these tools to show that recent (syntactic) testability results indeed provide an infiniti number of infinity strict hierarchies of (semantically) distinct testable locally characterized linear-invariant properties.

  • 13. Bhatttacharyya, Arnab
    et al.
    Grigorescu, Elena
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Xie, Ning
    On the Semantics of Local Characterizations for Linear-Invariant Properties2011Conference paper (Refereed)
    Abstract [en]

    A property of functions on a vector space is said to be linear-invariant if it is closed under linear transformations of the domain. Linear-invariant properties are some of the most well-studied properties in the field of property testing. Testable linear-invariant properties can always be characterized by socalled local constraints, and of late there has been a rapidly developing body of research investigating the testability of linear-invariant properties in terms of their descriptions using such local constraints. One problematic aspect that has been largely ignored in this line of research, however, is that syntactically distinct local characterizations need not at all correspond to semantically distinct properties. In fact, there are known fairly dramatic examples where seemingly infinite families of properties collapse into a small finite set that was already well-understood. In this work, we therefore initiate a systematic study of the semantics of local characterizations of linear-invariant properties. For such properties the local characterizations have an especially nice structure in terms of forbidden patterns on linearly dependent sets of vectors, which can be encoded formally as matroid constraints. We develop techniques for determining, given two such matroid constraints, whether these constraints encode identical or distinct properties, and show for a fairly broad class of properties that these techniques provide necessary and sufficient conditions for deciding between the two cases. We use these tools to show that recent (syntactic) testability results indeed provide an infinite number of infinite strict hierarchies of (semantically) distinct testable locally characterized linear-invariant properties

  • 14. Chan, S. M.
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordstrom, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Hardness of Approximation in PSPACE and Separation Results for Pebble Games2015In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Institute of Electrical and Electronics Engineers (IEEE), 2015, p. 466-485Conference paper (Refereed)
    Abstract [en]

    We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond - Tompa and Raz - McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.

  • 15.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Meir, Or
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Toniann, Pitassi
    Robere, Robert
    Vinyals, Marc
    Lifting with Simple Gadgets and Applications to Circuit and Proof ComplexityManuscript (preprint) (Other academic)
    Abstract [en]

    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 greater-than. 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 non-explicit 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.

  • 16.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS. Univ Copenhagen, Copenhagen, Denmark.
    Meir, Or
    Univ Haifa, Haifa, Israel.
    Robere, Robert
    DIMACS, New Brunswick, NJ USA.
    Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling2019In: Proceedings of the 34th Annual Computational Complexity Conference (CCC ’19), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2019, Vol. 137, p. 18:1-18:16Conference paper (Refereed)
    Abstract [en]

    We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if an only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.

  • 17.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Risse, Kilian
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Sokolov, Dmitry
    Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs2020In: 35th Computational Complexity Conference (CCC 2020), Schloss Dagstuhl–Leibniz-Zentrum für Informatik , 2020, Vol. 169, p. 28-1Conference paper (Refereed)
  • 18.
    de Rezende, Susanna F.
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)2016In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2016, Vol. 2016, p. 295-304Conference paper (Refereed)
    Abstract [en]

    We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers. We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajicek ' 98], drawing on and extending techniques in [Raz and McKenzie ' 99] and [Goos et al. '15]. The communication lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic graphs. As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain an exponential separation between monotone-AC(i-1) and monotone-AC(i), improving exponentially over the superpolynomial separation in [Raz and McKenzie ' 99]. That is, we give an explicit Boolean function that can be computed by monotone Boolean circuits of depth log(i) n and polynomial size, but for which circuits of depth O (log(i-1) n) require exponential size.

  • 19. Elffers, J.
    et al.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    A cardinal improvement to pseudo-boolean solving2020In: AAAI 2020 - 34th AAAI Conference on Artificial Intelligence, AAAI press , 2020, p. 1495-1503Conference paper (Refereed)
    Abstract [en]

    Pseudo-Boolean solvers hold out the theoretical potential of exponential improvements over conflict-driven clause learning (CDCL) SAT solvers, but in practice perform very poorly if the input is given in the standard conjunctive normal form (CNF) format. We present a technique to remedy this problem by recovering cardinality constraints from CNF on the fly during search. This is done by collecting potential building blocks of cardinality constraints during propagation and combining these blocks during conflict analysis. Our implementation has a non-negligible but manageable overhead when detection is not successful, and yields significant gains for some SAT competition and crafted benchmarks for which pseudo-Boolean reasoning is stronger than CDCL. It also boosts performance for some native pseudo-Boolean formulas where this approach helps to improve learned constraints. Copyright

  • 20.
    Elffers, Jan
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Giráldez-Cru, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Vinyals, Marc
    Tata Institute of Fundamental Research, Mumbai, India.
    Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers2018In: Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018, Springer, 2018, Vol. 10929, p. 75-93Conference paper (Refereed)
    Abstract [en]

    We study cdcl-cuttingplanes, Open-WBO, and Sat4j, three successful solvers from the Pseudo-Boolean Competition 2016, and evaluate them by performing experiments on crafted benchmarks designed to be trivial for the cutting planes (CP) proof system underlying pseudo-Boolean (PB) proof search but yet potentially tricky for PB solvers. Our experiments demonstrate severe shortcomings in state-of-the-art PB solving techniques. Although our benchmarks have linear-size tree-like CP proofs, and are thus extremely easy in theory, the solvers often perform quite badly even for very small instances. We believe this shows that solvers need to employ stronger rules of cutting planes reasoning. Even some instances that lack not only Boolean but also real-valued solutions are very hard in practice, which indicates that PB solvers need to get better not only at Boolean reasoning but also at linear programming. Taken together, our results point to several crucial challenges to be overcome in the quest for more efficient pseudo-Boolean solvers, and we expect that a further study of our benchmarks could shed more light on the potential and limitations of current state-of-the-art PB solving.

  • 21.
    Elffers, Jan
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Giráldez-Crú, Jesús
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Gocht, Stephan
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Simon, L.
    Université de Bordeaux, France.
    Seeking practical CDCL insights from theoretical SAT benchmarks2018In: IJCAI International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2018, p. 1300-1308Conference paper (Refereed)
    Abstract [en]

    Over the last decades Boolean satisfiability (SAT) solvers based on conflict-driven clause learning (CDCL) have developed to the point where they can handle formulas with millions of variables. Yet a deeper understanding of how these solvers can be so successful has remained elusive. In this work we shed light on CDCL performance by using theoretical benchmarks, which have the attractive features of being a) scalable, b) extremal with respect to different proof search parameters, and c) theoretically easy in the sense of having short proofs in the resolution proof system underlying CDCL. This allows for a systematic study of solver heuristics and how efficiently they search for proofs. We report results from extensive experiments on a wide range of benchmarks. Our findings include several examples where theory predicts and explains CDCL behaviour, but also raise a number of intriguing questions for further study.

  • 22.
    Elffers, Jan
    et al.
    Lund Univ, Lund, Sweden.;Univ Copenhagen, Copenhagen, Denmark..
    Gocht, Stephan
    Lund Univ, Lund, Sweden.;Univ Copenhagen, Copenhagen, Denmark..
    McCreesh, Ciaran
    Univ Glasgow, Glasgow, Lanark, Scotland..
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS. Univ Copenhagen, Copenhagen, Denmark.;KTH Royal Inst Technol, Stockholm, Sweden..
    Justifying All Differences Using Pseudo-Boolean Reasoning2020In: Thirty-Fourth Aaai Conference On Artificial Intelligence, The Thirty-Second Innovative Applications Of Artificial Intelligence Conference And The Tenth Aaai Symposium On Educational Advances In Artificial Intelligence, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE , 2020, p. 1486-1494Conference paper (Refereed)
    Abstract [en]

    Constraint programming solvers support rich global constraints and propagators, which make them both powerful and hard to debug. In the Boolean satisfiability community, proof-logging is the standard solution for generating trustworthy outputs, and this has become key to the social acceptability of computer-generated proofs. However, reusing this technology for constraint programming requires either much weaker propagation, or an impractical blowup in proof length. This paper demonstrates that simple, clean, and efficient proof logging is still possible for the all-different constraint, through pseudo-Boolean reasoning. We explain how such proofs can be expressed and verified mechanistically, describe an implementation, and discuss the broader implications for proof logging in constraint programming.

  • 23.
    Elffers, Jan
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Johannsen, J.
    Lauria, M.
    Magnard, T.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Trade-offs between time and memory in a tighter model of CDCL SAT solvers2016In: 19th International Conference on Theory and Applications of Satisfiability Testing, SAT 2016, Springer, 2016, p. 160-176Conference paper (Refereed)
    Abstract [en]

    A long line of research has studied the power of conflict- driven clause learning (CDCL) and how it compares to the resolution proof system in which it searches for proofs. It has been shown that CDCL can polynomially simulate resolution even with an adversarially chosen learning scheme as long as it is asserting. However, the simulation only works under the assumption that no learned clauses are ever forgot- ten, and the polynomial blow-up is significant. Moreover, the simulation requires very frequent restarts, whereas the power of CDCL with less frequent or entirely without restarts remains poorly understood. With a view towards obtaining results with tighter relations between CDCL and resolution, we introduce a more fine-grained model of CDCL that cap- tures not only time but also memory usage and number of restarts. We show how previously established strong size-space trade-offs for resolution can be transformed into equally strong trade-offs between time and memory usage for CDCL, where the upper bounds hold for CDCL with- out any restarts using the standard 1UIP clause learning scheme, and the (in some cases tightly matching) lower bounds hold for arbitrarily frequent restarts and arbitrary clause learning schemes.

  • 24.
    Elffers, Jan
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Divide and conquer: Towards faster pseudo-boolean solving2018In: IJCAI'18: Proceedings of the 27th International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2018, p. 1291-1299Conference paper (Refereed)
    Abstract [en]

    The last 20 years have seen dramatic improvements in the performance of algorithms for Boolean satisfiability-so-called SAT solvers-and today conflict-driven clause learning (CDCL) solvers are routinely used in a wide range of application areas. One serious short-coming of CDCL, however, is that the underlying method of reasoning is quite weak. A tantalizing solution is to instead use stronger pseudo-Boolean (PB) reasoning, but so far the promise of exponential gains in performance has failed to materialize-the increased theoretical strength seems hard to harness algorithmically, and in many applications CDCL-based methods are still superior. We propose a modified approach to pseudo-Boolean solving based on division instead of the saturation rule used in [Chai and Kuehlmann'05] and other PB solvers. In addition to resulting in a stronger conflict analysis, this also improves performance by keeping integer coefficient sizes down, and yields a very competitive solver as shown by the results in the Pseudo-Boolean Competitions 2015 and 2016.

  • 25. Filmus, Y.
    et al.
    Lauria, M.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Thapen, N.
    Ron-Zewi, N.
    Space complexity in polynomial calculus2012In: Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, IEEE , 2012, p. 334-344Conference paper (Refereed)
    Abstract [en]

    During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich et. al.'02], where the lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could refute any k-CNF formula in constant space. We prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied in [Alekhnovich et.al.~'02]. - For PCR, we prove an Omega(n) space lower bound for a bit wise encoding of the functional pigeonhole principle with m pigeons and n holes. These formulas have width O(log(n)), and hence this is an exponential improvement over [Alekhnovich et.al.~'02] measured in the width of the formulas. - We then present another encoding of the pigeonhole principle that has constant width, and prove an Omega(n) space lower bound in PCR for these formulas as well. - We prove an Omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHP(m, n) with m pigeons and n holes, and show that this is tight. - We prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not known to be the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way.

  • 26. Filmus, Y.
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mikša, Mladen
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, M.
    From small space to small width in resolution2015In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 16, no 4, article id 28Article in journal (Refereed)
    Abstract [en]

    In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of a Conjunctive Normal Form (CNF) formula is always an upper bound on the width needed to refute the formula. Their proof is beautiful but uses a nonconstructive argument based on Ehrenfeucht-Fraïssé games. We give an alternative, more explicit, proof that works by simple syntactic manipulations of resolution refutations. As a by-product, we develop a "black-box" technique for proving space lower bounds via a "static" complexitymeasure that works against any resolution refutation-previous techniques have been inherently adaptive. We conclude by showing that the related question for polynomial calculus (i.e., whether space is an upper bound on degree) seems unlikely to be resolvable by similarmethods.

  • 27. Filmus, Y.
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mikša, Mladen
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    From small space to small width in resolution2014In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2014, Vol. 25, p. 300-311Conference paper (Refereed)
    Abstract [en]

    In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools from finite model theory. We give an alternative, completely elementary, proof that works by simple syntactic manipulations of resolution refutations. As a by-product, we develop a "black-box" technique for proving space lower bounds via a "static" complexity measure that works against any resolution refutation-previous techniques have been inherently adaptive. We conclude by showing that the related question for polynomial calculus (i.e., whether space is an upper bound on degree) seems unlikely to be resolvable by similar methods.

  • 28. Filmus, Yuval
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mikša, Mladen
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Towards an understanding of polynomial calculus: New separations and lower bounds (extended abstract)2013In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, p. 437-448Conference paper (Refereed)
    Abstract [en]

    During the last decade, an active line of research in proof complexity has been into the space complexity of proofs and how space is related to other measures. By now these aspects of resolution are fairly well understood, but many open problems remain for the related but stronger polynomial calculus (PC/PCR) proof system. For instance, the space complexity of many standard "benchmark formulas" is still open, as well as the relation of space to size and degree in PC/PCR. We prove that if a formula requires large resolution width, then making XOR substitution yields a formula requiring large PCR space, providing some circumstantial evidence that degree might be a lower bound for space. More importantly, this immediately yields formulas that are very hard for space but very easy for size, exhibiting a size-space separation similar to what is known for resolution. Using related ideas, we show that if a graph has good expansion and in addition its edge set can be partitioned into short cycles, then the Tseitin formula over this graph requires large PCR space. In particular, Tseitin formulas over random 4-regular graphs almost surely require space at least Ω(√n). Our proofs use techniques recently introduced in [Bonacina-Galesi '13]. Our final contribution, however, is to show that these techniques provably cannot yield non-constant space lower bounds for the functional pigeonhole principle, delineating the limitations of this framework and suggesting that we are still far from characterizing PC/PCR space.

  • 29. Filmus, Yuval
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordstrom, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Ron-Zewi, Noga
    Thapen, Neil
    Space complexity in polynomial calculus2015In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 4, p. 1119-1153Article in journal (Refereed)
    Abstract [en]

    During the last 10 to 15 years, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important concern in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers. There has been a relatively long sequence of papers on space in resolution, which is now reasonably well-understood from this point of view. For other proof systems of interest, however, such as polynomial calculus or cutting planes, progress has been more limited. Essentially nothing has been known about space complexity in cutting planes, and for polynomial calculus the only lower bound has been for conjunctive normal form (CNF) formulas of unbounded width in [Alekhnovich et al., SIAM J. Comput., 31 (2002), pp. 1184-1211], where the space lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could be able to refute any k-CNF formula in constant space. In this paper, we prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied by Alekhnovich et al.: (1) We prove an omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHPmn with m pigeons and n holes, and show that this is tight. (2) For PCR, we prove an omega(n) space lower bound for a bitwise encoding of the functional pigeonhole principle. These formulas have width O(log n), and hence this is an exponential improvement over Alekhnovich et al. measured in the width of the formulas. (3) We then present another encoding of the pigeonhole principle that has constant width, and prove an omega(n) space lower bound in PCR for these formulas as well. (4) Finally, we prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not obviously the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way, something that we believe can be useful when proving PCR space lower bounds for other well-studied formula families in proof complexity.

  • 30. Filmus, Yuval
    et al.
    Lauria, Massimo
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Ron-Zewi, Noga
    Thapen, Neil
    Space Complexity in Polynomial Calculus2012In: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092, no 132Article in journal (Refereed)
    Abstract [en]

    During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers.

    There has been a relatively long sequence of papers on space in resolution, which is now reasonably well understood from this point of view.  For other natural candidates to study, however, such as polynomial calculus or cutting planes, very little has been known. We are not aware of any nontrivial space lower bounds for cutting planes, and for polynomial calculus the only lower bound has been for CNF formulas of unbounded width in [Alekhnovich et al. '02], where the space lower bound is smaller than the initial width of the clauses in the formulas.  Thus, in particular, it has been consistent with current knowledge that polynomial calculus could be able to refute any k-CNF formula in constant space.

    In this paper, we prove several new results on space in polynomial calculus (PC), and in the extended proof system polynomial calculus resolution (PCR) studied in [Alekhnovich et al. '02]:

    (1) We prove an Omega(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHP^m_n with m pigeons and n holes, and show that this is tight.

    (2) For PCR, we prove an Omega(n) space lower bound for a bitwise encoding of the functional pigeonhole principle.  These formulas have width O(log n), and hence this is an exponential improvement over [Alekhnovich et al. '02] measured in the width of the formulas.

    (3) We then present another encoding of the pigeonhole principle that has constant width, and prove an Omega(n) space lower bound in PCR for these formulas as well.

    (4) Finally, we prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not obviously the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way, something that we believe can be useful when proving PCR space lower bounds for other well-studied formula families in proof complexity.

  • 31.
    Gocht, Stephan
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS. University of Copenhagen, Denmark.
    Yehudayoff, Amir
    Technion - Israel Institute of Technology, Israel.
    On division versus saturation in pseudo-boolean solving2019In: IJCAI International Joint Conference on Artificial Intelligence: Volume 2019-August, 2019, 2019, p. 1711-1718Conference paper (Refereed)
    Abstract [en]

    The conflict-driven clause learning (CDCL) paradigm has revolutionized SAT solving over the last two decades. Extending this approach to pseudo-Boolean (PB) solvers doing 0-1 linear programming holds the promise of further exponential improvements in theory, but intriguingly such gains have not materialized in practice. Also intriguingly, most PB extensions of CDCL use not the division rule in cutting planes as defined in [Cook et al.,'87] but instead the so-called saturation rule. To the best of our knowledge, there has been no study comparing the strengths of division and saturation in the context of conflict-driven PB learning, when all linear combinations of inequalities are required to cancel variables. We show that PB solvers with division instead of saturation can be exponentially stronger. In the other direction, we prove that simulating a single saturation step can require an exponential number of divisions. We also perform some experiments to see whether these phenomena can be observed in actual solvers. Our conclusion is that a careful combination of division and saturation seems to be crucial to harness more of the power of cutting planes

  • 32. Huynh, Trinh
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity2012In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2012, p. 233-247Conference paper (Refereed)
    Abstract [en]

    An active line of research in proof complexity over the last decade has been the study of proof space and trade-offs between size and space. Such questions were originally motivated by practical SAT solving, but have also led to the development of new theoretical concepts in proof complexity of intrinsic interest and to results establishing nontrivial relations between space and other proof complexity measures. By now, the resolution proof system is fairly well understood in this regard, as witnessed by a sequence of papers leading up to [Ben-Sasson and Nordstrom 2008, 2011] and [Beame, Beck, and Impagliazzo 2012]. However, for other relevant proof systems in the context of SAT solving, such as polynomial calculus (PC) and cutting planes (CP), very little has been known. Inspired by [BN08, BN11], we consider CNF encodings of so-called pebble games played on graphs and the approach of making such pebbling formulas harder by simple syntactic modifications. We use this paradigm of hardness amplification to make progress on the relatively longstanding open question of proving time-space trade-offs for PC and CP. Namely, we exhibit a family of modified pebbling formulas {F n} n such that: • The formulas F n have size Θ(n) and width O(1). • They have proofs in length O(n) in resolution, which generalize to both PC and CP. • Any refutation in CP or PCR (a generalization of PC) in length L and space s must satisfy s log L > 4√n. A crucial technical ingredient in these results is a new two-player communication complexity lower bound for composed search problems in terms of block sensitivity, a contribution that we believe to be of independent interest.

  • 33. Järvisalo, M.
    et al.
    Matsliah, A.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Živný, S.
    Relating proof complexity measures and practical hardness of SAT2012In: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, p. 316-331Conference paper (Refereed)
    Abstract [en]

    Boolean satisfiability (SAT) solvers have improved enormously in performance over the last 10-15 years and are today an indispensable tool for solving a wide range of computational problems. However, our understanding of what makes SAT instances hard or easy in practice is still quite limited. A recent line of research in proof complexity has studied theoretical complexity measures such as length, width, and space in resolution, which is a proof system closely related to state-of-the-art conflict-driven clause learning (CDCL) SAT solvers. Although it seems like a natural question whether these complexity measures could be relevant for understanding the practical hardness of SAT instances, to date there has been very limited research on such possible connections. This paper sets out on a systematic study of the interconnections between theoretical complexity and practical SAT solver performance. Our main focus is on space complexity in resolution, and we report results from extensive experiments aimed at understanding to what extent this measure is correlated with hardness in practice. Our conclusion from the empirical data is that the resolution space complexity of a formula would seem to be a more fine-grained indicator of whether the formula is hard or easy than the length or width needed in a resolution proof. On the theory side, we prove a separation of general and tree-like resolution space, where the latter has been proposed before as a measure of practical hardness, and also show connections between resolution space and backdoor sets.

  • 34. Lagarde, G.
    et al.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Sokolov, D.
    Swernofsky, Jospeh Alexander
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Trade-offs between size and degree in polynomial calculus2020In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2020Conference paper (Refereed)
    Abstract [en]

    Building on [Clegg et al.’96], [Impagliazzo et al.’99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(n log S). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen’16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.

  • 35. Lauria, M.
    et al.
    Elffers, Jan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Vinyals, Marc
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    CNFgen: A generator of crafted benchmarks2017In: 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017, Springer, 2017, Vol. 10491, p. 464-473Conference paper (Refereed)
    Abstract [en]

    We present CNFgen, a generator of combinatorial benchmarks in DIMACS and OPB format. The proof complexity literature is a rich source not only of hard instances but also of instances that are theoretically easy but “extremal” in different ways, and therefore of potential interest in the context of SAT solving. Since most of these formulas appear not to be very well known in the SAT community, however, we propose CNFgen as a resource to make them readily available for solver development and evaluation. Many formulas studied in proof complexity are based on graphs, and CNFgen is also able to generate, parse and do basic manipulation of such objects. Furthermore, it includes a library cnfformula giving access to the functionality of CNFgen to Python programs.

  • 36. Lauria, M.
    et al.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases2017In: 32nd Computational Complexity Conference (CCC 2017), Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017, Vol. 79, article id 2Conference paper (Refereed)
    Abstract [en]

    We consider the graph k-colouring problem encoded as a set of polynomial equations in the standard way. We prove that there are bounded-degree graphs that do not have legal k-colourings but for which the polynomial calculus proof system defined in [Clegg et al. 1996, Alekhnovich et al. 2002] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gröbner bases solving graph k-colouring using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al. 2008, 2009, 2011, 2015] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned, e.g., in [De Loera et al. 2009] and [Li et al. 2016]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Miksa and Nordström 2015] with a reduction from FPHP to k-colouring derivable by polynomial calculus in constant degree.

  • 37.
    Lauria, Massimo
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Tight size-degree bounds for sums-of-squares proofs2015In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2015, Vol. 33, p. 448-466Conference paper (Refereed)
    Abstract [en]

    We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size nΩ(d) for values of d = d(n) from constant all the way up to nδ for some universal constant δ. This shows that the nO(d) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in [Krajícek’04] and [Dantchev and Riis’03], and then applying a restriction argument as in [Atserias, Müller, and Oliva’13] and [Atserias, Lauria, and Nordström’14]. This yields a generic method of amplifying SOS degree lower bounds to size lower bounds, and also generalizes the approach in [ALN14] to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.

  • 38. Lauria, Massimo
    et al.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Tight Size-Degree Bounds for Sums-of-Squares Proofs2017In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 26, no 4, p. 911-948Article in journal (Refereed)
    Abstract [en]

    We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size for values of d = d(n) from constant all the way up to for some universal constant . This shows that the running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in Krajiek (Arch Math Log 43(4):427-441, 2004) and Dantchev & Riis (Proceedings of the 17th international workshop on computer science logic (CSL '03), 2003) and then applying a restriction argument as in Atserias et al. (J Symb Log 80(2):450-476, 2015; ACM Trans Comput Log 17:19:1-19:30, 2016). This yields a generic method of amplifying SOS degree lower bounds to size lower bounds and also generalizes the approach used in Atserias et al. (2016) to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.

  • 39.
    Miksa, Mladen
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Long Proofs of (Seemingly) Simple Formulas2014In: THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, p. 121-137Conference paper (Refereed)
    Abstract [en]

    In 2010, Spence and Van Gelder presented a family of CNF formulas based on combinatorial block designs. They showed empirically that this construction yielded small instances that were orders of magnitude harder for state-of-the-art SAT solvers than other benchmarks of comparable size, but left open the problem of proving theoretical lower bounds. We establish that these formulas are exponentially hard for resolution and even for polynomial calculus, which extends resolution with algebraic reasoning. We also present updated experimental data showing that these formulas are indeed still hard for current CDCL solvers, provided that these solvers do not also reason in terms of cardinality constraints (in which case the formulas can become very easy). Somewhat intriguingly, however, the very hardest instances in practice seem to arise from so-called fixed bandwidth matrices, which are provably easy for resolution and are also simple in practice if the solver is given a hint about the right branching order to use. This would seem to suggest that CDCL with current heuristics does not always search efficiently for short resolution proofs, despite the theoretical results of [Pipatsrisawat and Darwiche 2011] and [Atserias, Fichte, and Thurley 2011].

  • 40.
    Mikša, Mladen
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A generalized method for proving polynomial calculus degree lower bounds2015In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2015, Vol. 33, p. 467-487Conference paper (Refereed)
    Abstract [en]

    We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. ’99] also on proof size. [Alekhnovich and Razborov’03] established that if the clause-variable incidence graph of a CNF formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further develop the techniques in [AR03] to show that if one can "cluster" clauses and variables in a way that "respects the structure" of the formula in a certain sense, then it is sufficient that the incidence graph of this clustered version is an expander. As a corollary of this, we prove that the functional pigeonhole principle (FPHP) formulas require high PC/PCR degree when restricted to constant-degree expander graphs. This answers an open question in [Razborov’02], and also implies that the standard CNF encoding of the FPHP formulas require exponential proof size in polynomial calculus resolution. Thus, while Onto-FPHP formulas are easy for polynomial calculus, as shown in [Riis’93], both FPHP and Onto-PHP formulas are hard even when restricted to bounded-degree expanders.

  • 41.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A (Biased) Proof Complexity Survey for SAT Practitioners2014In: THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, p. 1-6Conference paper (Refereed)
    Abstract [en]

    This talk is intended as a selective survey of proof complexity, focusing on some comparatively weak proof systems that are of particular interest in connection with SAT solving. We will review resolution, polynomial calculus, and cutting planes (related to conflict-driven clause learning, Grobner basis computations, and pseudo-Boolean solvers, respectively) and some proof complexity measures that have been studied for these proof systems. We will also briefly discuss if and how these proof complexity measures could provide insights into SAT solver performance.

  • 42.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A simplified way of proving trade-off results for resolution2009In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 109, no 18, p. 1030-1035Article in journal (Refereed)
    Abstract [en]

    We present a greatly simplified proof of the length-space trade-off result for resolution in [P. Hertel, T. Pitassi, Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '07), Oct. 2007, pp. 137-149], and also prove a couple of other theorems in the same vein. We point out two important ingredients needed for our proofs to work, and discuss some possible conclusions. Our key trick is to look at formulas of the type F = G ∧ H, where G and H are over disjoint sets of variables and have very different length-space properties with respect to resolution.

  • 43.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow proofs may be spacious: Separating space and width in resolution2006In: Proc. Annu. ACM Symp. Theory Comput., 2006, p. 507-516Conference paper (Refereed)
    Abstract [en]

    The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable CNF formulas. Also, the refutation space of a formula has been proven to be at least as large as the refutation width, but it has been open whether space can be separated from width or the two measures coincide asymptotically. We prove that there is a family of k-CNF formulas for which the refutation width in resolution is constant but the refutation space is non-constant, thus solving a problem mentioned in several previous papers.

  • 44.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Narrow proofs may be spacious: Separating space and width in resolution2009In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 39, no 1, p. 59-121Article in journal (Refereed)
    Abstract [en]

    The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable conjunctive normal form (CNF) formulas. Also, the minimum refutation space of a formula has been proven to be at least as large as the minimum refutation width, but it has been open whether space can be separated from width or the two measures coincide asymptotically. We prove that there is a family of k-CNF formulas for which the refutation width in resolution is constant but the refutation space is nonconstant, thus solving a problem mentioned in several previous papers.

  • 45.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On Proof Complexity Lower Bounds and Possible Connections to SAT Solving2011Conference paper (Refereed)
  • 46.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the Relative Strength of Pebbling and Resolution2012In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 13, no 2, p. 16-Article in journal (Refereed)
    Abstract [en]

    The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula and then argue that proofs of this formula must inherit (various aspects of) the pebbling properties of the underlying graph. Unfortunately, the reductions used here are not tight. To simulate resolution proofs by pebblings, the full strength of nondeterministic black-white pebbling is needed, whereas resolution is only known to be able to simulate deterministic black pebbling. To obtain strong results, one therefore needs to find specific graph families which either have essentially the same properties for black and black-white pebbling (not at all true in general) or which admit simulations of black-white pebblings in resolution. This article contributes to both these approaches. First, we design a restricted form of black-white pebbling that can be simulated in resolution and show that there are graph families for which such restricted pebblings can be asymptotically better than black pebblings. This proves that, perhaps somewhat unexpectedly, resolution can strictly beat black-only pebbling, and in particular that the space lower bounds on pebbling formulas in Ben-Sasson and Nordstr " om [2008] are tight. Second, we present a versatile parametrized graph family with essentially the same properties for black and black-white pebbling, which gives sharp simultaneous trade-offs for black and black-white pebbling for various parameter settings. Both of our contributions have been instrumental in obtaining the time-space trade-off results for resolution-based proof systems in Ben-Sasson and Nordstr " om [2011].

  • 47.
    Nordström, Jakob
    Massachusetts Institute of Technology.
    On the Relative Strength of Pebbling and Resolution2010In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC '10), 2010, p. 151-162Conference paper (Refereed)
    Abstract [en]

    The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula and then argue that proofs of this formula must inherit (various aspects of) the pebbling properties of the underlying graph. Unfortunately, the reductions used here are not tight. To simulate resolution proofs by pebblings, the full strength of nondeterministic black-white pebbling is needed, whereas resolution is only known to be able to simulate deterministic black pebbling. To obtain strong results, one therefore needs to find specific graph families which either have essentially the same properties for black and blackwhite pebbling (not at all true in general) or which admit simulations of black-white pebblings in resolution. This paper contributes to both these approaches. First, we design a restricted form of black-white pebbling that can be simulated in resolution and show that there are graph families for which such restricted pebblings can be asymptotically better than black pebblings. This proves that, perhaps somewhat unexpectedly, resolution can strictly beat black-only pebbling, and in particular that the space lower bounds on pebbling formulas in [Ben-Sasson and Nordstr¨om 2008] are tight. Second, we present a versatile parametrized graph family with essentially the same properties for black and black-white pebbling, which gives sharp simultaneous trade-offs for black and black-white pebbling for various parameter settings. Both of our contributions have been instrumental in obtaining the time-space trade-off results for resolution-based proof systems in [Ben-Sasson and Nordstr¨om 2009].

  • 48.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Pebble games, proof complexity, and time-space trade-offs2013In: Logical Methods in Computer Science, E-ISSN 1860-5974, Vol. 9, no 3, p. 15-Article in journal (Refereed)
    Abstract [en]

    Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. This is a survey of research in proof complexity drawing on results and tools from pebbling, with a focus on proof space lower bounds and trade-offs between proof size and proof space.

  • 49.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Short Proofs May Be Spacious: Understanding Space in Resolution2008Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The two main bottlenecks for such algorithms are the amounts of time and memory used. Thus, understanding time and memory requirements for clause learning algorithms, and how these requirements are related to one another, is a question of considerable practical importance.

    In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There has been a long line of research investigating these proof complexity measures and relating them to the width of proofs, another measure which has turned out to be intimately connected with both length and space. Formally, the length of a resolution proof is the number of lines, i.e., clauses, the width of a proof is the maximal size of any clause in it, and the space is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory.

    While strong results have been established for length and width, our understanding of space has been quite poor. For instance, the space required to prove a formula is known to be at least as large as the needed width, but it has remained open whether space can be separated from width or whether the two measures coincide asymptotically. It has also been unknown whether the fact that a formula is provable in short length implies that it is also provable in small space (which is the case for length versus width), or whether on the contrary these measures are "completely unrelated" in the sense that short proofs can be maximally complex with respect to space.

    In this thesis, as an easy first observation we present a simplified proof of the recent length-space trade-off result for resolution in (Hertel and Pitassi 2007) and show how our ideas can be used to prove a couple of other exponential trade-offs in resolution.

    Next, we prove that there are families of CNF formulas that can be proven in linear length and constant width but require space growing logarithmically in the formula size, later improving this exponentially to the square root of the size. These results thus separate space and width. Using a related but different approach, we then resolve the question about the relation between space and length by proving an optimal separation between them. More precisely, we show that there are families of CNF formulas of size O(n) that have resolution proofs of length O(n) and width O(1) but for which any proof requires space Omega(n/log n). All of these results are achieved by studying so-called pebbling formulas defined in terms of pebble games over directed acyclic graphs (DAGs) and proving lower bounds on the space requirements for such formulas in terms of the black-white pebbling price of the underlying DAGs.

    Finally, we observe that our optimal separation of space and length is in fact a special case of a more general phenomenon. Namely, for any CNF formula F and any Boolean function f:{0,1}^d->{0,1}, replace every variable x in F by f(x_1, ..., x_d) and rewrite this new formula in CNF in the natural way, denoting the resulting formula F[f]. Then if F and f have the right properties, F[f] can be proven in resolution in essentially the same length and width as F but the minimal space needed for F[f] is lower-bounded by the number of variables that have to be mentioned simultaneously in any proof for F.

    Download full text (pdf)
    FULLTEXT01
  • 50.
    Nordström, Jakob
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Understanding the Hardness of Proving Formulas in Propositional Logic2011Conference paper (Refereed)
12 1 - 50 of 56
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf