Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ilario Bonacina:

TR16-057 | 11th April 2016
Ilario Bonacina

Total space in Resolution is at least width squared

Given an unsatisfiable $k$-CNF formula $\phi$ we consider two complexity measures in Resolution: width and total space. The width is the minimal $W$ such that there exists a Resolution refutation of $\phi$ with clauses of at most $W$ literals. The total space is the minimal size $T$ of a memory ... more >>>

TR15-133 | 12th August 2015
Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

Lower bounds: from circuits to QBF proof systems

A general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. Although there are famous examples where a transfer from ideas and techniques from ... more >>>

TR14-146 | 6th November 2014
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

Space proof complexity for random $3$-CNFs via a $(2-\epsilon)$-Hall's Theorem

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>

TR14-038 | 24th March 2014
Ilario Bonacina, Nicola Galesi, Neil Thapen

Total space in resolution

Revisions: 1

We show $\Omega(n^2)$ lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables, and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the long-standing open problem of whether there are families of $k$-CNF formulas of size $O(n)$ ... more >>>

TR12-119 | 24th September 2012
Ilario Bonacina, Nicola Galesi

Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems

We devise a new combinatorial characterization for proving space lower bounds in algebraic systems like Polynomial Calculus (Pc) and Polynomial Calculus with Resolution (Pcr). Our method can be thought as a Spoiler-Duplicator game, which is capturing boolean reasoning on polynomials instead that clauses as in the case of Resolution. Hence, ... more >>>

ISSN 1433-8092 | Imprint