Ramamohan Paturi

Available identifiers

zbMath Open paturi.ramamohanWikidataQ102109717 ScholiaQ102109717MaRDI QIDQ192223

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q5111351	2020-05-27	Paper
Subquadratic algorithms for succinct stable matching	2019-05-21	Paper
A satisfiability algorithm for \(\mathrm{AC}^0\)	2019-05-10	Paper
On problems as hard as CNF-SAT	2018-11-05	Paper
Beating brute force for systems of polynomial equations over finite fields	2018-07-16	Paper
Beating brute force for (quantified) satisfiability of circuits of bounded treewidth	2018-03-15	Paper
Subquadratic algorithms for succinct stable matching	2016-07-25	Paper
Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility	2016-04-15	Paper
Size-depth trade-offs for threshold circuits	2015-05-07	Paper
Jealousy graphs: structure and complexity of decentralized stable matching	2015-01-12	Paper
On the complexity of circuit satisfiability	2014-08-13	Paper
Finding heavy hitters from lossy or noisy data	2013-10-04	Paper
On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}	2013-05-16	Paper
Common Knowledge and State-Dependent Equilibria	2013-03-13	Paper
On the exact complexity of evaluating quantified \(k\)-CNF	2010-12-07	Paper
Uniquely satisfiable \(k\)-SAT instances with almost minimal occurrences of each variable	2010-09-29	Paper
The complexity of satisfiability of small depth circuits	2010-01-14	Paper
k-SAT Is No Harder Than Decision-Unique-k-SAT	2009-08-18	Paper
An improved exponential-time algorithm for k -SAT	2008-12-21	Paper
The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs	2008-03-11	Paper
https://portal.mardi4nfdi.de/entity/Q5460925	2005-07-20	Paper
On the complexity of \(k\)-SAT	2002-08-14	Paper
Which problems have strongly exponential complexity?	2002-07-04	Paper
Scalable network architectures using the optical transpose interconnection system (OTIS)	2001-10-01	Paper
https://portal.mardi4nfdi.de/entity/Q4526973	2001-02-28	Paper
Exponential lower bounds for depth three Boolean circuits	2000-12-19	Paper
https://portal.mardi4nfdi.de/entity/Q4484662	2000-05-29	Paper
Dimension of Projections in Boolean Functions	1998-09-21	Paper
Size--Depth Tradeoffs for Threshold Circuits	1997-05-26	Paper
Approximating threshold circuits by rational functions	1995-08-27	Paper
The light bulb problem	1995-07-06	Paper
Effect of connectivity in an associative memory model	1994-01-06	Paper
https://portal.mardi4nfdi.de/entity/Q4013544	1992-09-27	Paper
Milking the Aanderaa argument	1990-01-01	Paper
There are no p-complete families of symmetric Boolean functions	1989-01-01	Paper
Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques	1988-01-01	Paper
Probabilistic communication complexity	1986-01-01	Paper

Research outcomes over time

This page was built for person: Ramamohan Paturi