Chris Calabro

According to our database, Chris Calabro authored at least 7 papers between 2006 and 2013.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2013

On the Exact Complexity of Evaluating Quantified <i>k</i> -CNF.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Algorithmica, 2013

2009

The exponential complexity of satisfiability problems.

Chris Calabro

PhD thesis, 2009

The Complexity of Satisfiability of Small Depth Circuits.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

<i>k</i>-SAT Is No Harder Than Decision-Unique-<i>k</i>-SAT.

Chris Calabro, Ramamohan Paturi

Proceedings of the Computer Science, 2009

2008

The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.

Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi

J. Comput. Syst. Sci., 2008

A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths.

Chris Calabro

Electron. Colloquium Comput. Complex., 2008

2006

A Duality between Clause Width and Clause Density for SAT.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006