Massimo Lauria

Jakob Nordström

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies.

[BibT_eX]

[DOI]

Lorenzo Carlucci

ACM Trans. Comput. Log., 2016

Semantic Versus Syntactic Cutting Planes.

[BibT_eX]

[DOI]

Yuval Filmus

Pavel Hrubes

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

2015

Hardness of Approximation in PSPACE and Separation Results for Pebble Games.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Tight Size-Degree Bounds for Sums-of-Squares Proofs.

[BibT_eX]

[DOI]

Jakob Nordström

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

From Small Space to Small Width in Resolution.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

Narrow Proofs May Be Maximally Long.

[BibT_eX]

[DOI]

Albert Atserias

Jakob Nordström

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Short $\mathsf{Res}^*(\mathsf{polylog})$ refutations if and only if narrow $\mathsf{Res}$ refutations.

[BibT_eX]

[DOI]

CoRR, 2013

A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2013, 2013

The Complexity of Proving That a Graph Is Ramsey.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

A rank lower bound for cutting planes proofs of Ramsey Theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

A Characterization of Tree-Like Resolution Size.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Space Complexity in Polynomial Calculus.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Parameterized Complexity of DPLL Search Procedures.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2011, 2011

Parameterized Bounded-Depth Frege Is Not Optimal.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Paris-Harrington Tautologies.

[BibT_eX]

[DOI]

Lorenzo Carlucci

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Optimality of size-degree tradeoffs for polynomial calculus.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2010

On the Automatizability of Polynomial Calculus.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Hardness of Parameterized Resolution.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

2009

Random CNFs require spacious Polynomial Calculus refutations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2007

On the bounded-hop MST problem on random Euclidean instances.

[BibT_eX]

Theor. Comput. Sci., 2007

Extending Polynomial Calculus to $k$-DNF Resolution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks.

[BibT_eX]

[DOI]

Tiziana Calamoneri

Proceedings of the Structural Information and Communication Complexity, 2006

A Distributed Protocol for the Bounded-Hops Converge-Cast in Ad-Hoc Networks.

[BibT_eX]

[DOI]

Proceedings of the Ad-Hoc, Mobile, and Wireless Networks, 5th International Conference, 2006

2005

Divide and Conquer Is Almost Optimal for the Bounded-Hop MST Problem on Random Euclidean Instances.

[BibT_eX]

[DOI]