Ramamohan Paturi

AAAI Conference 2026 Conference Paper

Quiet Feature Learning in Algorithmic Tasks

• Prudhviraj Naidu
• Zixian Wang
• Leon Bergen
• Ramamohan Paturi

We train Transformer-based language models on ten foundational algorithmic tasks and observe pronounced phase transitions in their loss curves that deviate from established power-law scaling trends. Over large ranges of compute, the validation loss barely improves, then abruptly decreases. Probing the models’ internal representations reveals that quiet features are learned prior to any decrease in task loss. These quiet features represent intermediate algorithmic computations that do not by themselves improve the output loss. Ablation experiments demonstrate that individual quiet features are causally necessary for task performance. Our results demonstrate that substantial representational progress can remain hidden beneath an apparently flat loss curve, challenging the prevailing use of cross‑entropy as a proxy for learning and motivating richer diagnostics for monitoring model training.

NeurIPS Conference 2023 Conference Paper

Scientific Document Retrieval using Multi-level Aspect-based Queries

• Jianyou (Andre) Wang
• Kaicheng Wang
• Xiaoyue Wang
• Prudhviraj Naidu
• Leon Bergen
• Ramamohan Paturi

In scientific research, the ability to effectively retrieve relevant documents based on complex, multifaceted queries is critical. Existing evaluation datasets for this task are limited, primarily due to the high costs and effort required to annotate resources that effectively represent complex queries. To address this, we propose a novel task, $\textbf{S}$cientific $\textbf{Do}$cument $\textbf{R}$etrieval using $\textbf{M}$ulti-level $\textbf{A}$spect-based qu$\textbf{E}$ries (DORIS-MAE), which is designed to handle the complex nature of user queries in scientific research. We developed a benchmark dataset within the field of computer science, consisting of 100 human-authored complex query cases. For each complex query, we assembled a collection of 100 relevant documents and produced annotated relevance scores for ranking them. Recognizing the significant labor of expert annotation, we also introduce Anno-GPT, a scalable framework for evaluating the viability of Large Language Models (LLMs) such as ChatGPT-3. 5 for expert-level dataset annotation tasks. The application of Anno-GPT to annotate the DORIS-MAE dataset resulted in a 500x reduction in cost, without compromising quality. Furthermore, due to the multi-tiered structure of these complex queries, our DORIS-MAE dataset can be extended to over 4, 000 sub-query test cases without requiring additional annotation. We evaluated 17 recent retrieval methods on DORIS-MAE, observing notable performance drops compared to traditional datasets. This highlights DORIS-MAE's challenges and the need for better approaches to handle complex, multifaceted queries in scientific research. Our dataset and codebase are available at https: //github. com/Real-Doris-Mae/Doris-Mae-Dataset.

SODA Conference 2018 Conference Paper

Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth

• Daniel Lokshtanov
• Ivan Mikhailin
• Ramamohan Paturi
• Pavel Pudlák

SODA Conference 2017 Conference Paper

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

• Daniel Lokshtanov
• Ramamohan Paturi
• Suguru Tamaki
• R. Ryan Williams
• Huacheng Yu

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≤ 2 and finite field q where q = p d for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O ( q n ) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time q n + o ( n ) · q − n / O ( k ) time if q < 2 4 ekd, and otherwise, where e = 2. 718… is Napier's constant, and a deterministic algorithm for counting solutions with running time q n + o ( n ) · q − n / O ( kq 6/7 d ). For the important special case of quadratic equations in F 2, our randomized algorithm has running time O (2 0. 8765n ). For systems over 2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a ΣΠΣ circuit, i. e. , a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2 n-dn for δ = 1/ O (log(s/ n )) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O (log(s/ n )).

FOCS Conference 2013 Conference Paper

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

• Russell Impagliazzo
• Ramamohan Paturi
• Stefan Schneider 0003

We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.

SODA Conference 2012 Conference Paper

A satisfiability algorithm for AC 0

• Russell Impagliazzo
• William Matthews
• Ramamohan Paturi

We consider the problem of efficiently enumerating the satisfying assignments to AC 0 circuits. We give a zero-error randomized algorithm which takes an AC 0 circuit as input and constructs a set of restrictions which partitions {0, 1} n so that under each restriction the value of the circuit is constant. Let d denote the depth of the circuit and cn denote the number of gates. This algorithm runs in time | C |2 n (1 − μ c, d ) where | C | is the size of the circuit for μ c, d ≥ 1/O[lg c + d lg d ] d − 1 with probability at least 1 − 2 − n. As a result, we get improved exponential time algorithms for AC 0 circuit satisfiability and for counting solutions. In addition, we get an improved bound on the correlation of AC 0 circuits with parity. As an important component of our analysis, we extend the Håstad Switching Lemma to handle multiple k - cnf s and k - dnf s.

SAT Conference 2010 Invited Paper

Exact Algorithms and Complexity

• Ramamohan Paturi

Abstract Over the past couple of decades, a series of exact exponential-time algorithms have been developed with improved run times for a number of problems including IndependentSet, k-SAT, and k -colorability using a variety of algorithmic techniques such as backtracking, dynamic programming, and inclusion-exclusion. The series of improvements are typically in the form of better exponents compared to exhaustive search. These improvements prompt several questions, chief among them is whether we can expect continued improvements in the exponent. Is there a limit beyond which one should not expect improvement? If we assume NP ≠ P or other appropriate complexity statement, what can we say about the likely exact complexities of various NP-complete problems?

STOC Conference 2010 Conference Paper

On the complexity of circuit satisfiability

• Ramamohan Paturi
• Pavel Pudlák

SAT Conference 2010 Conference Paper

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

• William Matthews
• Ramamohan Paturi

Abstract Let ( k, s )- SAT refer the family of satisfiability problems restricted to CNF formulas with exactly k distinct literals per clause and at most s occurrences of each variable. Kratochvíl, Savický and Tuza [6] show that there exists a function f ( k ) such that for all s ≤ f ( k ), all ( k, s )- SAT instances are satisfiable whereas for k ≥ 3 and s > f ( k ), ( k, s )- SAT is NP -complete. We define a new function u ( k ) as the minimum s such that uniquely satisfiable ( k, s )- SAT formulas exist. We show that for k ≥ 3, unique solutions and NP -hardness occur at almost the same value of s: f ( k ) ≤ u ( k ) ≤ f ( k ) + 2. We also give a parsimonious reduction from SAT to ( k, s )- SAT for any k ≥ 3 and s ≥ f ( k ) + 2. When combined with the Valiant–Vazirani Theorem [8], this gives a randomized polynomial time reduction from SAT to UNIQUE -( k, s )- SAT.

FOCS Conference 1998 Conference Paper

An Improved Exponential-Time Algorithm for k -SAT

• Ramamohan Paturi
• Pavel Pudlák
• Michael E. Saks
• Francis Zane

We propose and analyze a simple new algorithm for finding satisfying assignments of Boolean formulae in conjunctive normal form. The algorithm, ResolveSat, is a randomized variant of the DDL procedure by M. Davis et al. (1962) or Davis-Putnam procedure. Rather than applying the DLL procedure to the input formula F, however; ResolveSat enlarges F by adding additional clauses using limited resolution before performing DLL. The basic idea behind our analysis is the same as by R. Paturi (1997): a critical clause for a variable at a satisfying assignment gives rise to a unit clause in the DLL procedure with sufficiently high probability, thus increasing the probability of finding a satisfying assignment. In the current paper, we analyze the effect of multiple critical clauses (obtained through resolution) in producing unit clauses. We show that, for each k, the running time of ResolveSat on a k-CNF formula is significantly better than 2/sup n/, even in the worst case. In particular we show that the algorithm finds a satisfying assignment of a general 3-CNF in time O(2/sup. 446n/) with high probability; where the best previous algorithm has running time O(2/sup. 582n/). We obtain a better upper bound of O(2/sup (2ln2-1)/n+0(n))=O(2/sup 0. 387n/) for 3-CNF that have at most one satisfying assignment (unique k-SAT). For each k, the bounds for general k-CNF are the best known for the worst-case complexity of finding a satisfying solution for k-SAT, the idea of succinctly encoding satisfying solutions can be applied to obtain lower bounds on circuit site. Here, we exhibit a function f such that any depth-3 AND-OR circuit with bottom fan-in bounded by k requires /spl Omega/(2(c/sub k/n/k)) gates (with c/sub k/>1). This is the first such lower bound with c/sub k/>1.

FOCS Conference 1998 Conference Paper

Which Problems Have Strongly Exponential Complexity?

• Russell Impagliazzo
• Ramamohan Paturi
• Francis Zane

For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction which we call sub-exponential reduction family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP-search problems, and that for any fixed k, k-SAT, k-Colorability, k-Set Cover Independent Set, Clique, Vertex Cover are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others. We also look at the issue of proving strongly exponential lower bounds (that is, bounds of the form 2/sup /spl Omega/(n)/) for AC/sup 0/. This problem is even open far depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most n/sup /spl epsiv//) fan-infer bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even degree 2 random GF(2) polynomials require strongly exponential site for /spl Sigma//sub 3//sup k/ circuits for k=o(loglogn). We thus exhibit a much smaller space of 2(0(/sup n2/)) functions such that almost every function in this class requires strongly exponential size /spl Sigma//sub 3//sup k/ circuits. As a corollary, we derive a pseudorandom generator (requiring O(n/sup 2/) bits of advice) that maps n bits into a larger number of bits so that computing parity on the range is hard for /spl Sigma//sub 3//sup k/ circuits. Our main technical lemma is an algorithm that, for any fixed /spl epsiv/>0, represents an arbitrary k-CNF formula as a disjunction of 2/sup /spl epsiv/n/ k-CNF formulas that are sparse, e. g. , each having O(n) clauses.

STOC Conference 1997 Conference Paper

Exponential Lower Bounds for Depth 3 Boolean Circuits

• Ramamohan Paturi
• Michael E. Saks
• Francis Zane

FOCS Conference 1997 Conference Paper

Satisfiability Coding Lemma

• Ramamohan Paturi
• Pavel Pudlák
• Francis Zane

We present and analyze two simple algorithms for finding satisfying assignments of /spl kappa/-CNFs (Boolean formulae in conjunctive normal form with at most /spl kappa/ literals per clause). The first is a randomized algorithm which, with probability approaching 1, finds a satisfying assignment of a satisfiable /spl kappa/-CNF formula F in time O(n/sup 2/|F|2/sup n-n//spl kappa//). The second algorithm is deterministic, and its running time approaches 2/sup n-n/2/spl kappa// for large n and /spl kappa/. The randomized algorithm is the best known algorithm for /spl kappa/>3; the deterministic algorithm is the best known deterministic algorithm for /spl kappa/>4. We also show an /spl Omega/(n/sup 1/4/2/sup /spl radic/n/) lower bound on the size of depth 3 circuits of AND and OR gates computing the parity function. This bound is tight up to a constant factor. The key idea used in these upper and lower bounds is what we call the Satisfiability Coding Lemma. This basic lemma shows how to encode satisfying solutions of a /spl kappa/-CNF succinctly.

STOC Conference 1993 Conference Paper

Size-depth trade-offs for threshold circuits

• Russell Impagliazzo
• Ramamohan Paturi
• Michael E. Saks

STOC Conference 1992 Conference Paper

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

• Ramamohan Paturi

I&C Journal 1990 Journal Article

Milking the Aanderaa argument

• Ramamohan Paturi
• Joel I. Seiferas
• Janos Simon
• Richard E. Newman-Wolfe

FOCS Conference 1990 Conference Paper

On Threshold Circuits for Parity

• Ramamohan Paturi
• Michael E. Saks

Motivated by, the problem of understanding the limitations of neural networks for representing Boolean functions, the authors consider size-depth tradeoffs for threshold circuits that compute the parity function. They give an almost optimal lower bound on the number of edges of any depth-2 threshold circuit that computes the parity function with polynomially bounded weights. The main technique used in the proof, which is based on the theory of rational approximation, appears to be a potentially useful technique for the analysis of such networks. It is conjectured that there are no linear size, bounded-depth threshold circuits for computing parity. >

FOCS Conference 1988 Conference Paper

Effect of Connectivity in Associative Memory Models (Preliminary Version)

• János Komlós
• Ramamohan Paturi

The authors investigate how good connectivity properties translate into good error-correcting behavior in sparse networks of threshold elements. They determine how the eigenvalues of the interconnection graph (which in turn reflect connectivity properties) relate to the quantities, number of items stored, amount of error-correction, radius of attraction, and rate of convergence in an associative memory model consisting of a sparse network of threshold elements or neurons. >

FOCS Conference 1984 Conference Paper

Probabilistic Communication Complexity (Preliminary Version)

• Ramamohan Paturi
• Janos Simon

We study (unbounded error) probabilistic communication complexity. Our new results include -one way and two complexities differ by at most 1 - certain functions like equality and the verification of Hamming distance have upper bounds that are considerably better than their counterparts in deterministic, nondeterministic, or bounded error probabilistic model - there exists a function which requires /spl Omega/(logn) information transfer. As an application, we prove that a certain language requires /spl Omega/(nlogn) time to be recognized by a 1-tape (unbounded error) probabilistic Turing machine. This bound is optimal. (Previous lower bound results [Yao 1] require acceptance by bounded error computation. We believe that this is the first nontrivial lower bound on the time required by unrestricted probabilistic Turing machines.

FOCS Conference 1983 Conference Paper

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

• Ramamohan Paturi
• Janos Simon

We study probabilistic on-line simulators for several machine models (or memory structures). The simulators have a more constrained access to data than the virtual machines, but are allowed to use probabilistic means to improve average access time. We show that in many cases coin tosses can not make up for inadequate access.