Ramamohan Paturi

93 papers A* 24A 9B 3C 1Misc 1Journal 47Unranked 5
YearRankTypeTitle / Venue / Authors
2026 J jnl
Optimal Depth-Three Circuits for Inner Product.
CoRR
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher D. Rosin, Navid Talebanfard
2026 J jnl
Optimal Monotone Depth-Three Circuit Lower Bounds for Majority.
CoRR
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher D. Rosin, Michael E. Saks, Navid Talebanfard
2026 A* conf
Quiet Feature Learning in Algorithmic Tasks.
AAAI
Prudhviraj Naidu, Zixian Wang, Leon Bergen, Ramamohan Paturi
2025 J jnl
EvidenceBench: A Benchmark for Extracting Evidence from Biomedical Papers.
CoRR
Jianyou Wang, Weili Cao, Kaicheng Wang, Xiaoyue Wang, Ashish Dalvi, Gino Prasad, Qishan Liang, Hsuan-lin Her, Ming Wang, Qin Yang, Gene W. Yeo, David E. Neal, Maxim Khan, Christopher D. Rosin, Ramamohan Paturi, Leon Bergen
2025 A conf
Local Enumeration: The Not-All-Equal Case.
STACS
Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, Navid Talebanfard
2025 J jnl
Local Enumeration: The Not-All-Equal Case.
CoRR
Mohit Gurumukhani, Ramamohan Paturi, Michael E. Saks, Navid Talebanfard
2025 A* conf
Measuring Risk of Bias in Biomedical Reports: The RoBBR Benchmark.
EMNLP
Jianyou Wang, Weili Cao, Longtian Bao, Youze Zheng, Gil Pasternak, Kaicheng Wang, Xiaoyue Wang, Ramamohan Paturi, Leon Bergen
2025 J jnl
Quiet Feature Learning in Algorithmic Tasks.
CoRR
Prudhviraj Naidu, Zixian Wang, Leon Bergen, Ramamohan Paturi
2025 J jnl
Single-Pass Document Scanning for Question Answering.
CoRR
Weili Cao, Jianyou Wang, Youze Zheng, Longtian Bao, Qirui Zheng, Taylor Berg-Kirkpatrick, Ramamohan Paturi, Leon Bergen
2024 J jnl
BIRCO: A Benchmark of Information Retrieval Tasks with Complex Objectives.
CoRR
Xiaoyue Wang, Jianyou Wang, Weili Cao, Kaicheng Wang, Ramamohan Paturi, Leon Bergen
2024 J jnl
Dissociation of Faithful and Unfaithful Reasoning in LLMs.
CoRR
Evelyn Yee, Alice Li, Chenyu Tang, Yeon Ho Jung, Ramamohan Paturi, Leon Bergen
2024 — conf
IR2: Information Regularization for Information Retrieval.
LREC/COLING
Jianyou Wang, Kaicheng Wang, Xiaoyue Wang, Weili Cao, Ramamohan Paturi, Leon Bergen
2024 J jnl
IR2: Information Regularization for Information Retrieval.
CoRR
Jianyou Wang, Kaicheng Wang, Xiaoyue Wang, Weili Cao, Ramamohan Paturi, Leon Bergen
2024 A conf
Local Enumeration and Majority Lower Bounds.
CCC
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
2024 J jnl
Local Enumeration and Majority Lower Bounds.
CoRR
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
2024 J jnl
Measuring Risk of Bias in Biomedical Reports: The RoBBR Benchmark.
CoRR
Jianyou Wang, Weili Cao, Longtian Bao, Youze Zheng, Gil Pasternak, Kaicheng Wang, Xiaoyue Wang, Ramamohan Paturi, Leon Bergen
2024 J jnl
On Extremal Properties of k-CNF: Capturing Threshold Functions.
CoRR
Mohit Gurumukhani, Marvin Künnemann, Ramamohan Paturi
2023 J jnl
DORIS-MAE: Scientific Document Retrieval using Multi-level Aspect-based Queries.
CoRR
Jianyou Wang, Kaicheng Wang, Xiaoyue Wang, Prudhviraj Naidu, Leon Bergen, Ramamohan Paturi
2023 A* conf
Scientific Document Retrieval using Multi-level Aspect-based Queries.
NeurIPS
Jianyou Wang, Kaicheng Wang, Xiaoyue Wang, Prudhviraj Naidu, Leon Bergen, Ramamohan Paturi
2019 J jnl
Subquadratic Algorithms for Succinct Stable Matching.
Algorithmica
Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider
2018 A* conf
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.
SODA
Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlák
2017 A* conf
Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
SODA
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu
2017 A* conf
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming.
ICALP
Marvin Künnemann, Ramamohan Paturi, Stefan Schneider
2017 J jnl
On the Fine-grained Complexity of One-Dimensional Dynamic Programming.
CoRR
Marvin Künnemann, Ramamohan Paturi, Stefan Schneider
2016 — ch.
Backtracking Based
Encyclopedia of Algorithms
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2016 A conf
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility.
ITCS
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
2016 J jnl
On Problems as Hard as CNF-SAT.
ACM Trans. Algorithms
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2016 Misc conf
Subquadratic Algorithms for Succinct Stable Matching.
CSR
Daniel Moeller, Ramamohan Paturi, Stefan Schneider
2015 J jnl
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility.
Electron. Colloquium Comput. Complex.
Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider
2015 J jnl
Subquadratic Algorithms for Succinct Stable Matching.
CoRR
Daniel Moeller, Ramamohan Paturi, Stefan Schneider
2014 J jnl
0-1 Integer Linear Programming with a Linear Number of Constraints.
CoRR
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
2014 J jnl
0-1 Integer Linear Programming with a Linear Number of Constraints.
Electron. Colloquium Comput. Complex.
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
2013 A* conf
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits.
FOCS
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
2013 B conf
Exact Complexity and Satisfiability - (Invited Talk).
IPEC
Russell Impagliazzo, Ramamohan Paturi
2013 J jnl
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).
Dagstuhl Reports
Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams
2013 — conf
Finding Heavy Hitters from Lossy or Noisy Data.
APPROX-RANDOM
Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi
2013 — conf
Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching.
WINE
Moshe Hoffman, Daniel Moeller, Ramamohan Paturi
2013 J jnl
On the Exact Complexity of Evaluating Quantified
Algorithmica
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2012 J jnl
A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits
CoRR
Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider
2012 A* conf
A satisfiability algorithm for AC
SODA
Russell Impagliazzo, William Matthews, Ramamohan Paturi
2012 B conf
Common Knowledge and State-Dependent Equilibria.
SAGT
Nuh Aygün Dalkiran, Moshe Hoffman, Ramamohan Paturi, Daniel Ricketts, Andrea Vattani
2012 J jnl
Experimental study of the impact of historical information in human coordination
CoRR
Manuel Cebrián, Ramamohan Paturi, Daniel Ricketts
2012 A conf
On Problems as Hard as CNF-SAT.
CCC
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2011 J jnl
A Satisfiability Algorithm for AC$^0$
CoRR
Russell Impagliazzo, William Matthews, Ramamohan Paturi
2011 A* conf
Does more connectivity help groups to solve social problems.
EC
Daniel P. Enemark, Mathew D. McCubbins, Ramamohan Paturi, Nicholas Weller
2011 J jnl
On Problems as Hard as CNFSAT
CoRR
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
2010 — conf
10441 Abstracts Collection - Exact Complexity of NP-hard Problems.
Exact Complexity of NP-hard Problems
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin
2010 A conf
Exact Algorithms and Complexity.
SAT
Ramamohan Paturi
2010 — ed.
Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010
Exact Complexity of NP-hard Problems
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin
2010 C conf
Low Memory Distributed Protocols for 2-Coloring.
SSS
Amos Israeli, Mathew D. McCubbins, Ramamohan Paturi, Andrea Vattani
2010 B conf
On the Exact Complexity of Evaluating Quantified
IPEC
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2010 A* conf
On the complexity of circuit satisfiability.
STOC
Ramamohan Paturi, Pavel Pudlák
2010 A conf
Uniquely Satisfiable
SAT
William Matthews, Ramamohan Paturi
2009 — conf
The Complexity of Satisfiability of Small Depth Circuits.
IWPEC
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2008 — ch.
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2008 J jnl
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.
J. Comput. Syst. Sci.
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2008 A* conf
Xl: an efficient network routing algorithm.
SIGCOMM
Kirill Levchenko, Geoffrey M. Voelker, Ramamohan Paturi, Stefan Savage
2006 A conf
A Duality between Clause Width and Clause Density for SAT.
CCC
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
2005 J jnl
An improved exponential-time algorithm for
J. ACM
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2004 J jnl
Circuit lower bounds and linear codes
Electron. Colloquium Comput. Complex.
Ramamohan Paturi, Pavel Pudlák
2004 A* conf
On the difficulty of scalably detecting network attacks.
CCS
Kirill Levchenko, Ramamohan Paturi, George Varghese
2003 A conf
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.
CCC
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi
2001 J jnl
On the Complexity of k-SAT.
J. Comput. Syst. Sci.
Russell Impagliazzo, Ramamohan Paturi
2001 J jnl
Which Problems Have Strongly Exponential Complexity?
J. Comput. Syst. Sci.
Russell Impagliazzo, Ramamohan Paturi, Francis Zane
2000 J jnl
Exponential lower bounds for depth three Boolean circuits.
Comput. Complex.
Ramamohan Paturi, Michael E. Saks, Francis Zane
2000 J jnl
Scalable Network Architectures Using the Optical Transpose Interconnection System (OTIS).
J. Parallel Distributed Comput.
Francis Zane, Philippe J. Marchand, Ramamohan Paturi, Sadik C. Esener
1999 A conf
Complexity of k-SAT.
CCC
Russell Impagliazzo, Ramamohan Paturi
1999 J jnl
Satisfiability Coding Lemma.
Chic. J. Theor. Comput. Sci.
Ramamohan Paturi, Pavel Pudlák, Francis Zane
1998 A* conf
An Improved Exponential-Time Algorithm for
FOCS
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
1998 J jnl
Dimension of Projections in Boolean Functions.
SIAM J. Discret. Math.
Ramamohan Paturi, Francis Zane
1998 A* conf
Which Problems Have Strongly Exponential Complexity?
FOCS
Russell Impagliazzo, Ramamohan Paturi, Francis Zane
1997 A* conf
Exponential Lower Bounds for Depth 3 Boolean Circuits.
STOC
Ramamohan Paturi, Michael E. Saks, Francis Zane
1997 A* conf
Satisfiability Coding Lemma.
FOCS
Ramamohan Paturi, Pavel Pudlák, Francis Zane
1997 J jnl
Size-Depth Tradeoffs for Threshold Circuits.
SIAM J. Comput.
Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1996 J jnl
Discrete Neural Computation: A Theoretical Foundation [Book Review].
IEEE Trans. Neural Networks
Ramamohan Paturi
1996 J jnl
Solving the net matching problem in high-performance chip design.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
Robert J. Carragher, Chung-Kuan Cheng, Xiao-Ming Xiong, Masahiro Fujita, Ramamohan Paturi
1995 J jnl
The Light Bulb Problem
Inf. Comput.
Ramamohan Paturi, Sanguthevar Rajasekaran, John H. Reif
1994 J jnl
Approximating Threshold Circuits by Rational Functions
Inf. Comput.
Ramamohan Paturi, Michael E. Saks
1994 J jnl
Program Speedup in a Heterogeneous Computing Network.
J. Parallel Distributed Comput.
Val Donaldson, Francine Berman, Ramamohan Paturi
1993 J jnl
Effect of Connectivity in an Associative Memory Model.
J. Comput. Syst. Sci.
János Komlós, Ramamohan Paturi
1993 A* conf
Size-depth trade-offs for threshold circuits.
STOC
Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1992 A* conf
On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version)
STOC
Ramamohan Paturi
1990 J jnl
Milking the Aanderaa Argument
Inf. Comput.
Ramamohan Paturi, Joel I. Seiferas, Janos Simon, Richard E. Newman-Wolfe
1990 A* conf
On Threshold Circuits for Parity
FOCS
Ramamohan Paturi, Michael E. Saks
1990 A* conf
On Threshold Circuits for Parity (Abstract).
COLT
Ramamohan Paturi, Michael E. Saks
1989 A* conf
The Light Bulb Problem.
COLT
Ramamohan Paturi, Sanguthevar Rajasekaran, John H. Reif
1989 J jnl
There are no p-Complete Families of Symmetric Boolean Functions.
Inf. Process. Lett.
Mihály Geréb-Graus, Ramamohan Paturi, Endre Szemerédi
1988 J jnl
Convergence results in an associative memory model.
Neural Networks
János Komlós, Ramamohan Paturi
1988 A* conf
Effect of Connectivity in Associative Memory Models (Preliminary Version)
FOCS
János Komlós, Ramamohan Paturi
1988 J jnl
Universal Traversal Sequences of Length n^O(log n) for Cliques.
Inf. Process. Lett.
Howard J. Karloff, Ramamohan Paturi, Janos Simon
1986 J jnl
Probabilistic Communication Complexity.
J. Comput. Syst. Sci.
Ramamohan Paturi, Janos Simon
1984 A* conf
Probabilistic Communication Complexity (Preliminary Version)
FOCS
Ramamohan Paturi, Janos Simon
1983 A* conf
Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version)
FOCS
Ramamohan Paturi, Janos Simon