1 citations · 3 across the 5 of their papers we have counts for
7 papers
A Logspace-Constructive Proof of L=SL
Sam Buss, Anant Dhayal, Valentine Kabanets +2
We formalize the proof of Reingold's Theorem that SL=L [Rei05] in the theory of bounded arithmetic VL, which corresponds to ``logspace reasoning''. As a consequence, we get that VL…
Limits of CDCL Learning via Merge Resolution
Marc Vinyals, Chunxiao Li, Noah Fleming +2
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. Howeve…
Learning with distributional inverters
Eric Binnendyk, Marco Carmosino, Antonina Kolokolova +2
We generalize the "indirect learning" technique of Furst et. al., 1991 to reduce from learning a concept class over a samplable distribution to learning the same concept class…
On the Hierarchical Community Structure of Practical Boolean Formulas
Chunxiao Li, Jonathan Chung, Soham Mukherjee +5
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…
GANs & Reels: Creating Irish Music using a Generative Adversarial Network
Antonina Kolokolova, Mitchell Billard, Robert Bishop +5
In this paper we present a method for algorithmic melody generation using a generative adversarial network without recurrent components. Music generation has been successfully done…
Stabbing Planes
Paul Beame, Noah Fleming, Russell Impagliazzo +4
We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based mode…
Approximating solution structure of the Weighted Sentence Alignment problem
Antonina Kolokolova, Renesa Nizamee
We study the complexity of approximating solution structure of the bijective weighted sentence alignment problem of DeNero and Klein (2008). In particular, we consider the complexi…