Marc Vinyals
YOU?
Author Swipe
View article: Irreducible Subcube Partitions
Irreducible Subcube Partitions Open
A subcube partition is a partition of the Boolean cube $\{0,1\}^n$ into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are singletons and the entire partition. A subcube partition is tight …
View article: Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Hardness of Approximation in PSPACE and Separation Results for Pebble Games Open
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 numbe…
View article: Limits of CDCL Learning via Merge Resolution
Limits of CDCL Learning via Merge Resolution Open
In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simu…
View article: Proving Unsatisfiability with Hitting Formulas
Proving Unsatisfiability with Hitting Formulas Open
Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultaneously falsified. [Peitl,Szeider,05] conjectured that hittin…
View article: Irreducible Subcube Partitions
Irreducible Subcube Partitions Open
A subcube partition is a partition of the Boolean cube {0,1}^n into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are singletons and the entire partition. A subcube partition is tight if i…
View article: MaxSAT Resolution and Subcube Sums
MaxSAT Resolution and Subcube Sums Open
We study the MaxSAT Resolution (MaxRes) rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p -simulates …
View article: On the Hierarchical Community Structure of Practical SAT Formulas
On the Hierarchical Community Structure of Practical SAT Formulas Open
Modern CDCL SAT solvers easily solve industrial instances containing tens of millions of variables and clauses, despite the theoretical intractability of the SAT problem. This gap between practice and theory is a central problem in solver …
View article: On the Hierarchical Community Structure of Practical Boolean Formulas
On the Hierarchical Community Structure of Practical Boolean Formulas Open
Modern CDCL SAT solvers easily solve industrial instances containing tens of millions of variables and clauses, despite the theoretical intractability of the SAT problem. This gap between practice and theory is a central problem in solver …
View article: Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract) Open
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a f…
View article: Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity Open
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 …
View article: Complexity Measures on the Symmetric Group and Beyond
Complexity Measures on the Symmetric Group and Beyond Open
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a f…
View article: MaxSAT Resolution and Subcube Sums
MaxSAT Resolution and Subcube Sums Open
We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution.…
View article: Hard Examples for Common Variable Decision Heuristics
Hard Examples for Common Variable Decision Heuristics Open
The CDCL algorithm for SAT is equivalent to the resolution proof system under a few assumptions, one of them being an optimal non-deterministic procedure for choosing the next variable to branch on. In practice this task is left to a varia…
View article: Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers Open
Restarts are a widely-used class of techniques integral to the efficiency of Conflict-Driven Clause Learning (CDCL) Boolean SAT solvers. While the utility of such policies has been well-established empirically, a theoretical explanation of…
View article: Lifting in Proof Complexity
Lifting in Proof Complexity Open
A growing number of results in proof complexity rely on so-called "lifting" techniques (also called hardness escalation"), which are inspired from communication complexity. In the context of proof complexity, the basic idea of lifting is s…
View article: MassimoLauria/cnfgen: CNFgen registered with Zenodo
MassimoLauria/cnfgen: CNFgen registered with Zenodo Open
CNFgen registered with Zenodo
View article: Equality Alone Does not Simulate Randomness
Equality Alone Does not Simulate Randomness Open
The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is "Equality". In this work we show that even allowing access to an "Eq…
View article: Space in Proof Complexity
Space in Proof Complexity Open
ropositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic. In this thesis we are concerned with the size and space of proofs, and in particular with the latter. Different approache…
View article: Cumulative Space in Black-White Pebbling and Resolution
Cumulative Space in Black-White Pebbling and Resolution Open
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 …