Ramamohan Paturi

According to our database1, Ramamohan Paturi authored at least 61 papers between 1983 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
Subquadratic Algorithms for Succinct Stable Matching.
Algorithmica, 2019

2018
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms, 2016

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Subquadratic Algorithms for Succinct Stable Matching.
Proceedings of the Computer Science - Theory and Applications, 2016

2014
0-1 Integer Linear Programming with a Linear Number of Constraints.
Electronic Colloquium on Computational Complexity (ECCC), 2014

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

On the Exact Complexity of Evaluating Quantified k -CNF.
Algorithmica, 2013

Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching.
Proceedings of the Web and Internet Economics - 9th International Conference, 2013

Exact Complexity and Satisfiability - (Invited Talk).
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Finding Heavy Hitters from Lossy or Noisy Data.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
A satisfiability algorithm for AC0.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Common Knowledge and State-Dependent Equilibria.
Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

On Problems as Hard as CNF-SAT.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Does more connectivity help groups to solve social problems.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010
On the complexity of circuit satisfiability.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Low Memory Distributed Protocols for 2-Coloring.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

Exact Algorithms and Complexity.
Proceedings of the Theory and Applications of Satisfiability Testing, 2010

Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable.
Proceedings of the Theory and Applications of Satisfiability Testing, 2010

On the Exact Complexity of Evaluating Quantified k-CNF.
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

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

2009
The Complexity of Satisfiability of Small Depth Circuits.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

k-SAT Is No Harder Than Decision-Unique-k-SAT.
Proceedings of the Computer Science, 2009

2008
Backtracking Based k-SAT Algorithms.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Xl: an efficient network routing algorithm.
Proceedings of the ACM SIGCOMM 2008 Conference on Applications, 2008

2006
A Duality between Clause Width and Clause Density for SAT.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2004
Circuit lower bounds and linear codes
Electronic Colloquium on Computational Complexity (ECCC), 2004

On the difficulty of scalably detecting network attacks.
Proceedings of the 11th ACM Conference on Computer and Communications Security, 2004

2003
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2001
On the Complexity of k-SAT.
J. Comput. Syst. Sci., 2001

2000
Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS).
J. Parallel Distrib. Comput., 2000

Exponential lower bounds for depth three Boolean circuits.
Computational Complexity, 2000

1999
Complexity of k-SAT.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Dimension of Projections in Boolean Functions.
SIAM J. Discrete Math., 1998

An Improved Exponential-Time Algorithm for k-SAT.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Which Problems Have Strongly Exponential Complexity?
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Size-Depth Tradeoffs for Threshold Circuits.
SIAM J. Comput., 1997

Exponential Lower Bounds for Depth 3 Boolean Circuits.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Satisfiability Coding Lemma.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Discrete Neural Computation: A Theoretical Foundation [Book Review].
IEEE Trans. Neural Networks, 1996

Solving the net matching problem in high-performance chip design.
IEEE Trans. on CAD of Integrated Circuits and Systems, 1996

1995
The Light Bulb Problem
Inf. Comput., March, 1995

1994
Approximating Threshold Circuits by Rational Functions
Inf. Comput., August, 1994

Program Speedup in a Heterogeneous Computing Network.
J. Parallel Distrib. Comput., 1994

1993
Effect of Connectivity in an Associative Memory Model.
J. Comput. Syst. Sci., 1993

Size-depth trade-offs for threshold circuits.
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)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1990
Milking the Aanderaa Argument
Inf. Comput., September, 1990

On Threshold Circuits for Parity
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On Threshold Circuits for Parity (Abstract).
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
There are no p-Complete Families of Symmetric Boolean Functions.
Inf. Process. Lett., 1989

The Light Bulb Problem.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988
Convergence results in an associative memory model.
Neural Networks, 1988

Universal Traversal Sequences of Length n^O(log n) for Cliques.
Inf. Process. Lett., 1988

Effect of Connectivity in Associative Memory Models (Preliminary Version)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1986
Probabilistic Communication Complexity.
J. Comput. Syst. Sci., 1986

1984
Probabilistic Communication Complexity (Preliminary Version)
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)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983


  Loading...