Source author record

Ramamohan Paturi

Ramamohan Paturi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Computation and Language Computer Science and Game Theory Logic in Computer Science Machine Learning physics.soc-ph Social and Information Networks

Catalog footprint

What is connected

6works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Quiet Feature Learning in Algorithmic Tasks

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.

preprint2016arXiv

Subquadratic Algorithms for Succinct Stable Matching

We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier and investigate other implications. We give subquadratic algorithms for finding a stable matching in special cases of natural succinct representations of the problem, the $d$-attribute, $d$-list, geometric, and single-peaked models. We also present algorithms for verifying a stable matching in the same models. We further show that for $d = ω(\log n)$ both finding and verifying a stable matching in the $d$-attribute and $d$-dimensional geometric models requires quadratic time assuming the Strong Exponential Time Hypothesis. This suggests that these succinct models are not significantly simpler computationally than the general case for sufficiently large $d$.

preprint2014arXiv

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

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where n is the number of variables and cn is the number of constraints. The key idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.

preprint2013arXiv

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

We give a nontrivial algorithm for the satisfiability problem for cn-wire threshold circuits of depth two which is better than exhaustive search by a factor 2^{sn} where s= 1/c^{O(c^2)}. We believe that this is the first nontrivial satisfiability algorithm for cn-wire threshold circuits of depth two. 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. 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 cn. One of our motivations is proving strong lower bounds for TC^0 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.

preprint2012arXiv

Experimental study of the impact of historical information in human coordination

We perform laboratory experiments to elucidate the role of historical information in games involving human coordination. Our approach follows prior work studying human network coordination using the task of graph coloring. We first motivate this research by showing empirical evidence that the resolution of coloring conflicts is dependent upon the recent local history of that conflict. We also conduct two tailored experiments to manipulate the game history that can be used by humans in order to determine (i) whether humans use historical information, and (ii) whether they use it effectively. In the first variant, during the course of each coloring task, the network positions of the subjects were periodically swapped while maintaining the global coloring state of the network. In the second variant, participants completed a series of 2-coloring tasks, some of which were restarts from checkpoints of previous tasks. Thus, the participants restarted the coloring task from a point in the middle of a previous task without knowledge of the history that led to that point. We report on the game dynamics and average completion times for the diverse graph topologies used in the swap and restart experiments.

preprint2011arXiv

A Satisfiability Algorithm for AC$^0$

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 partition $\{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} \ge 1/\bigO[\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 $\kcnf$s and $\kdnf$s.