Ramamohan Paturi

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

On Problems as Hard as CNF-SAT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Subquadratic Algorithms for Succinct Stable Matching.

[BibT_eX]

[DOI]

Daniel Moeller

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

0-1 Integer Linear Programming with a Linear Number of Constraints.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

On the Exact Complexity of Evaluating Quantified k -CNF.

[BibT_eX]

[DOI]

Algorithmica, 2013

Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching.

[BibT_eX]

[DOI]

Moshe Hoffman

Daniel Moeller

Proceedings of the Web and Internet Economics - 9th International Conference, 2013

Exact Complexity and Satisfiability - (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Finding Heavy Hitters from Lossy or Noisy Data.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits

[BibT_eX]

[DOI]

CoRR, 2012

Experimental study of the impact of historical information in human coordination

[BibT_eX]

[DOI]

Manuel Cebrián

Daniel Ricketts

CoRR, 2012

A satisfiability algorithm for AC0.

[BibT_eX]

[DOI]

William Matthews

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Common Knowledge and State-Dependent Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

2011

On Problems as Hard as CNFSAT

[BibT_eX]

[DOI]

CoRR, 2011

A Satisfiability Algorithm for AC$^0$

[BibT_eX]

[DOI]

William Matthews

CoRR, 2011

Does more connectivity help groups to solve social problems.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010

On the complexity of circuit satisfiability.

[BibT_eX]

[DOI]

Pavel Pudlák

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Low Memory Distributed Protocols for 2-Coloring.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

Exact Algorithms and Complexity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable.

[BibT_eX]

[DOI]

William Matthews

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

10441 Abstracts Collection - Exact Complexity of NP-hard Problems.

[BibT_eX]

[DOI]

Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

2009

The Complexity of Satisfiability of Small Depth Circuits.

[BibT_eX]

[DOI]

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

k-SAT Is No Harder Than Decision-Unique-k-SAT.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2009

2008

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Xl: an efficient network routing algorithm.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGCOMM 2008 Conference on Applications, 2008

2006

A Duality between Clause Width and Clause Density for SAT.

[BibT_eX]

[DOI]

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

2005

An improved exponential-time algorithm for k-SAT.

[BibT_eX]

[DOI]

J. ACM, 2005

2004

Circuit lower bounds and linear codes

[BibT_eX]

[DOI]

Pavel Pudlák

Electron. Colloquium Comput. Complex., 2004

On the difficulty of scalably detecting network attacks.

[BibT_eX]

[DOI]

Kirill Levchenko

George Varghese

Proceedings of the 11th ACM Conference on Computer and Communications Security, 2004

2001

Which Problems Have Strongly Exponential Complexity?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

On the Complexity of k-SAT.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

2000

Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS).

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2000

Exponential lower bounds for depth three Boolean circuits.

[BibT_eX]

[DOI]

Comput. Complex., 2000

1999

Satisfiability Coding Lemma.

[BibT_eX]

[DOI]

Pavel Pudlák

Chic. J. Theor. Comput. Sci., 1999

1998

Dimension of Projections in Boolean Functions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1998

1997

Size-Depth Tradeoffs for Threshold Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

Exponential Lower Bounds for Depth 3 Boolean Circuits.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Discrete Neural Computation: A Theoretical Foundation [Book Review].

[BibT_eX]

[DOI]

IEEE Trans. Neural Networks, 1996

Solving the net matching problem in high-performance chip design.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1996

1995

The Light Bulb Problem

[BibT_eX]

[DOI]

Sanguthevar Rajasekaran

John H. Reif

Inf. Comput., March, 1995

1994

Approximating Threshold Circuits by Rational Functions

[BibT_eX]

[DOI]

Inf. Comput., August, 1994

Program Speedup in a Heterogeneous Computing Network.

[BibT_eX]

[DOI]

Val Donaldson

Francine Berman

J. Parallel Distributed Comput., 1994

1993

Effect of Connectivity in an Associative Memory Model.

[BibT_eX]

[DOI]

János Komlós

J. Comput. Syst. Sci., 1993

Size-depth trade-offs for threshold circuits.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1990

Milking the Aanderaa Argument

[BibT_eX]

[DOI]

Joel I. Seiferas

Richard E. Newman-Wolfe

Inf. Comput., September, 1990

On Threshold Circuits for Parity

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On Threshold Circuits for Parity (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989

There are no p-Complete Families of Symmetric Boolean Functions.

[BibT_eX]

[DOI]

Mihály Geréb-Graus

Endre Szemerédi

Inf. Process. Lett., 1989

1988

Convergence results in an associative memory model.

[BibT_eX]

[DOI]

János Komlós

Neural Networks, 1988

Universal Traversal Sequences of Length n^O(log n) for Cliques.

[BibT_eX]

[DOI]

Howard J. Karloff

Inf. Process. Lett., 1988

Effect of Connectivity in Associative Memory Models (Preliminary Version)

[BibT_eX]

[DOI]

János Komlós

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1986

Probabilistic Communication Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1986

1984

Probabilistic Communication Complexity (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version)

[BibT_eX]

[DOI]