Rahul Santhanam

FOCS Conference 2024 Conference Paper

On the Complexity of Avoiding Heavy Elements

• Zhenjian Lu
• Igor C. Oliveira 0001
• Hanlin Ren
• Rahul Santhanam

We introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N)\geq 1/$ poly $(N)$ fixed in advance, output an $N$ -bit string that has probability less than $\delta(N)$. We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization. Among other results, we show: 1)For a wide range of circuit classes $\mathcal{C}$, including $\text{ACC}^{0}, \text{TC}^{0}, \text{NC}^{1}$ and general Boolean circuits, EX P does not have uniform randomized C-circuits if and only if Heavy Avoid for uniform implicit C -samplers has efficient deterministic algorithms infinitely often. This gives the first algorithmic characterization of lower bounds for EXP against uniform randomized low-depth circuits. We show similar algorithmic characterizations for lower bounds in PSPACE, NP and $\text{EXP}^{\text{NP}}$. 2)Unconditionally, there are polynomial-time pseudodeterministic algorithms that work infinitely often for several variants of Heavy Avoid, such as for uniform samplers of small randomness complexity. In contrast, the existence of a similar algorithm that solves Heavy Avoid for arbitrary polynomial-time samplers would solve a long-standing problem about hierarchies for probabilistic time. 3)If there is a time and depth efficient deterministic algorithm for Heavy Avoid, then $BPP=P$. Without the depth-efficiency requirement in the assumption, we still obtain a non-trivial form of infinitely-often deterministic simulation of randomized algorithms. These results are shown using non-black-box reductions, and we argue that the use of non-black-box reductions is essential here. The full version is available on ECCC [1].

FOCS Conference 2023 Conference Paper

Polynomial-Time Pseudodeterministic Construction of Primes

• Lijie Chen 0001
• Zhenjian Lu
• Igor C. Oliveira 0001
• Hanlin Ren
• Rahul Santhanam

A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser [1] posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an unconditional polynomial-time randomized algorithm B such that, for infinitely many values of $n, B\left(1^{n}\right)$ outputs a canonical n-bit prime $p_{n}$ with high probability. More generally, we prove that for every dense property Q of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying Q. This improves upon a subexponential-time construction of Oliveira and Santhanam [2]. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell [3], using a variant of the Shaltiel-Umans generator [4].

FOCS Conference 2022 Conference Paper

On the Range Avoidance Problem for Circuits

• Hanlin Ren
• Rahul Santhanam
• Zhikun Wang

We consider the range avoidance problem (called Avoid): given the description of a circuit with more output gates than input gates, find a string that is not in the range of the circuit. This problem is complete for the class APEPP that corresponds to explicit constructions of objects whose existence follows from the probabilistic method (Korten, FOCS 2021). Motivated by applications in explicit constructions and complexity theory, we initiate the study of the range avoidance problem for weak circuit classes, and obtain the following results: 1)Generalising Williams’s connections between circuitanalysis algorithms and circuit lower bounds (J. ACM 2014), we present a framework for solving $\mathscr{C}$-Avoid in FP NP using circuit-analysis data structures for $\mathscr{C}$, for “typical” multi-output circuit classes $\mathscr{C}$. As an application, we present a non-trivial FP NP range avoidance algorithm for De Morgan formulas. /inlp>An important technical ingredient is a construction of rectangular PCPs of proximity, building on the rectangular PCPs by Bhangale, Harsha, Paradise, and Tal (FOCS 2020). 2)Using the above framework, we show that circuit lower bounds for E NP are equivalent to circuit-analysis algorithms with E NP preprocessing. This is the first equivalence result regarding circuit lower bounds for E NP. Our equivalences have the additional advantages that they work in both infinitely-often and almost-everywhere settings, and that they also hold for larger (e. g. , subexponential) size bounds. 3)Complementing the above results, we show that in some settings, solving $\mathscr{C}$-Avoid would imply breakthrough lower bounds, even for very weak circuit classes $\mathscr{C}$. In particular, an algorithm for AC 0 -Avoid with polynomial stretch implies lower bounds against NC 1, and an algorithm for $NC_{4}^{0}$-Avoid with very small stretch implies lower bounds against NC 1 and branching programs. 4)We show that Avoid is in FNP if and only if there is a propositional proof system that breaks every non-uniform proof complexity generator. This result connects the study of range avoidance with fundamental questions in proof complexity.

STOC Conference 2022 Conference Paper

Robustness of average-case meta-complexity via pseudorandomness

• Rahul Ilango
• Hanlin Ren
• Rahul Santhanam

We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide range of parameters (various thresholds, approximation gaps, weak or strong average-case hardness, etc.) and complexity notions, showing the theory of meta-complexity is very *robust* in the average-case setting. Our results are shown by establishing new and generic connections between meta-complexity and the theory of pseudorandomness and one-way functions. Using these connections, we give the first unconditional characterization of one-way functions based on the average-case hardness of the Minimum Circuit Size Problem. We also give a surprising and clean characterization of one-way functions based on the average-case hardness of (the worst-case uncomputable) Kolmogorov complexity. Moreover, the latter is the first characterization of one-way functions based on the average-case hardness of a fixed problem on *any* samplable distribution. We give various applications of these results to the foundations of cryptography and the theory of meta-complexity. For example, we show that the average-case hardness of deciding k - SAT or Clique on any samplable distribution of high enough entropy implies the existence of one-way functions. We also use our results to unconditionally solve various meta-complexity problems in CZK (computational zero-knowledge) on average, and give implications of our results for the classic question of proving NP -hardness for the Minimum Circuit Size Problem.

FOCS Conference 2021 Conference Paper

Constructive Separations and Their Consequences

• Lijie Chen 0001
• Ce Jin 0001
• Rahul Santhanam
• R. Ryan Williams

For a complexity class C and language L, a constructive separation of “L is not in C” gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that “constructiveness” serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against P, ZPP, and BPP. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. For many separations, making them constructive would imply breakthrough lower bounds. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions $\mathbf{t}$, there are no constructive separations for detecting high t-time Kolmogorov complexity (a task which is known to be not in P) from any complexity class, unconditionally. We also show that under plausible conjectures, there are languages in NP - $\mathbf{P}$ for which there are no constructive separations from any complexity class.

STOC Conference 2021 Conference Paper

Iterated lower bound formulas: a diagonalization-based approach to proof complexity

• Rahul Santhanam
• Iddo Tzameret

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally. We use the approach to give an explicit sequence of CNF formulas {φ n } such that VNP ≠ VP iff there are no polynomial-size IPS proofs for the formulas φ n . This provides a natural equivalence between proof complexity lower bounds and standard algebraic complexity lower bounds. Our proof of this fact uses the implication from IPS lower bounds to algebraic complexity lower bounds due to Grochow and Pitassi together with a diagonalization argument: the formulas φ n themselves assert the non-existence of short IPS proofs for formulas encoding VNP ≠ VP at a different input length. Our result also has meta-mathematical implications: it gives evidence for the difficulty of proving strong lower bounds for IPS within IPS. For any strong enough propositional proof system R , we define the *iterated R -lower bound formulas*, which inductively assert the non-existence of short R proofs for formulas encoding the same statement at a different input length, and propose them as explicit hard candidates for the proof system R . We observe that this hypothesis holds for Resolution following recent results of Atserias and Muller and of Garlik, and give evidence in favour of it for other proof systems.

STOC Conference 2021 Conference Paper

Pseudodeterministic algorithms and the structure of probabilistic time

• Zhenjian Lu
• Igor C. Oliveira 0001
• Rahul Santhanam

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows. A new pseudorandom generator and its consequences. We build on techniques developed to prove hierarchy theorems for probabilistic time with advice (Fortnow and Santhanam, FOCS 2004) to construct the first unconditional pseudorandom generator of polynomial stretch computable in pseudodeterministic polynomial time (with one bit of advice) that is secure infinitely often against polynomial-time computations. As an application of this construction, we obtain new results about the complexity of generating and representing prime numbers. For instance, we show unconditionally for each ε > 0 that infinitely many primes p n have a succinct representation in the following sense: there is a fixed probabilistic polynomial time algorithm that generates p n with high probability from its succinct representation of size O (| p n | ε ). This offers an exponential improvement over the running time of previous results, and shows that infinitely many primes have succinct and efficient representations. Structural results for probabilistic time from pseudodeterministic algorithms. Oliveira and Santhanam (STOC 2017) established unconditionally that there is a pseudodeterministic algorithm for the Circuit Acceptance Probability Problem (CAPP) that runs in sub-exponential time and is correct with high probability over any samplable distribution on circuits on infinitely many input lengths. We show that improving this running time or obtaining a result that holds for every large input length would imply new time hierarchy theorems for probabilistic time. In addition, we prove that a worst-case polynomial-time pseudodeterministic algorithm for CAPP would imply that BPP has complete problems. Equivalence between pseudodeterministic constructions and hierarchies. We establish an equivalence between a certain explicit pseudodeterministic construction problem and the existence of strong hierarchy theorems for probabilistic time. More precisely, we show that pseudodeterministically constructing in exponential time strings of large rKt complexity (Oliveira, ICALP 2019) is possible if and only if for every constructive function T ( n ) ≤ exp( o (exp( n ))) we have BPTIME[poly( T )] ⊈ i.o.BPTIME[ T ]/log T . More generally, these results suggest new approaches for designing pseudodeterministic algorithms for search problems and for unveiling the structure of probabilistic time.

STOC Conference 2021 Conference Paper

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly

• Ján Pich
• Rahul Santhanam

FOCS Conference 2019 Conference Paper

Why are Proof Complexity Lower Bounds Hard?

• Ján Pich
• Rahul Santhanam

We formalize and study the question of whether there are inherent difficulties to showing lower bounds on propositional proof complexity. We establish the following unconditional result: Propositional proof systems cannot efficiently show that truth tables of random Boolean functions lack polynomial size non-uniform proofs of hardness. Assuming a conjecture of Rudich, propositional proof systems also cannot efficiently show that random k-CNFs of linear density lack polynomial size non-uniform proofs of unsatisfiability. Since the statements in question assert the average-case hardness of standard NP problems (MCSP and 3-SAT respectively) against co-nondeterministic circuits for natural distributions, one interpretation of our result is that propositional proof systems are inherently incapable of efficiently proving strong complexity lower bounds in our formalization. Another interpretation is that an analogue of the Razborov-Rudich `natural proofs' barrier holds in proof complexity: under reasonable hardness assumptions, there are natural distributions on hard tautologies for which it is infeasible to show proof complexity lower bounds for strong enough proof systems. For the specific case of the Extended Frege (EF) propositional proof system, we show that at least one of the following cases holds: (1) EF has no efficient proofs of superpolynomial circuit lower bound tautologies for any Boolean function or (2) There is an explicit family of tautologies of each length such that under reasonable hardness assumptions, most tautologies are hard but no propositional proof system can efficiently establish hardness for most tautologies in the family. Thus, under reasonable hardness assumptions, either the Circuit Lower Bounds program toward complexity separations cannot be implemented in EF, or there are inherent obstacles to implementing the Cook-Reckhow program for EF.

MFCS Conference 2018 Conference Paper

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds

• Ninad Rajgopal
• Rahul Santhanam
• Srikanth Srinivasan 0001

We give a deterministic algorithm for counting the number of satisfying assignments of any AC^0[oplus] circuit C of size s and depth d over n variables in time 2^(n-f(n, s, d)), where f(n, s, d) = n/O(log(s))^(d-1), whenever s = 2^o(n^(1/d)). As a consequence, we get that for each d, there is a language in E^{NP} that does not have AC^0[oplus] circuits of size 2^o(n^(1/(d+1))). This is the first lower bound in E^{NP} against AC^0[oplus] circuits that beats the lower bound of 2^Omega(n^(1/2(d-1))) due to Razborov and Smolensky for large d. Both our algorithm and our lower bounds extend to AC^0[p] circuits for any prime p.

FOCS Conference 2018 Conference Paper

Hardness Magnification for Natural Problems

• Igor C. Oliveira 0001
• Rahul Santhanam

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include: 1. Let MCSP be the decision problem whose YES instances are truth tables of functions with circuit complexity at most s(n). We show that if MCSP[2^√n] cannot be solved on average with zero error by formulas of linear (or even sub-linear) size, then NP does not have polynomial-size formulas. In contrast, Hirahara and Santhanam (2017) recently showed that MCSP[2^√n] cannot be solved in the worst case by formulas of nearly quadratic size. 2. If there is a c > 0 such that for each positive integer d there is an ε > 0 such that the problem of checking if an n-vertex graph in the adjacency matrix representation has a vertex cover of size (log n)^c cannot be solved by depth-d AC^0 circuits of size m^1+ε, where m = Θ(n^2), then NP does not have polynomial-size formulas. 3. Let (α, β)-MCSP[s] be the promise problem whose YES instances are truth tables of functions that are α-approximable by a circuit of size s(n), and whose NO instances are truth tables of functions that are not β-approximable by a circuit of size s(n). We show that for arbitrary 1/2 c, let MKtP[c, s] be the promise problem whose YES instances are strings of Kt complexity at most c(N) and NO instances are strings of Kt complexity greater than s(N). We show that if there is a δ > 0 such that for each ε > 0, MKtP[N^ε, N^ε + 5 log(N)] requires Boolean circuits of size N^1+δ, then EXP is not contained in SIZE (poly). For each of the cases of magnification above, we observe that standard hardness assumptions imply much stronger lower bounds for these problems than we require for magnification. We further explore magnification as an avenue to proving strong lower bounds, and argue that magnification circumvents the "natural proofs" barrier of Razborov and Rudich (1997). Examining some standard proof techniques, we find that they fall just short of proving lower bounds via magnification. As one of our main open problems, we ask whether there are other meta-mathematical barriers to proving lower bounds that rule out approaches combining magnification with known techniques.

STOC Conference 2017 Conference Paper

Pseudodeterministic constructions in subexponential time

• Igor C. Oliveira 0001
• Rahul Santhanam

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence { p n } of primes and a randomized algorithm A running in expected sub-exponential time such that for each n , on input 1 | p n | , A outputs p n with probability 1. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often. This result follows from a more general theorem about pseudodeterministic constructions. A property Q ⊆ {0,1} * is ϒ-dense if for large enough n , | Q ∩ {0,1} n | ≥ ϒ2 n . We show that for each c > 0 at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family { H n } of sets, H n ⊆ {0,1} n , such that for each (1/ n c )-dense property Q Ε DTIME ( n c ) and every large enough n , H n ∩ Q ≠ ∅ or (2) There is a deterministic sub-exponential time construction of a family { H ′ n } of sets, H ′ n ∩ {0,1} n , such that for each (1/ n c )-dense property Q Ε DTIME ( n c ) and for infinitely many values of n , H ′ n ∩ Q ≠ ∅. We provide further algorithmic applications that might be of independent interest. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.

I&C Journal 2017 Journal Article

Robust simulations and significant separations

• Lance Fortnow
• Rahul Santhanam

We define a new notion of “robust simulations” between complexity classes which is intermediate between the traditional notions of infinitely-often and almost-everywhere, as well as a corresponding notion of “significant separations”. A language L has a robust simulation in a complexity class C if there is a language in C which agrees with L on arbitrarily large polynomial stretches of input lengths. We show that various implications in complexity theory such as the collapse of PH if NP = P and the Karp–Lipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown. Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for non-deterministic polynomial time than the ones previously known.

SODA Conference 2015 Conference Paper

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity

• Rahul Santhanam
• R. Ryan Williams

We study algorithms for the satisfiability problem for quantified Boolean formulas (QBFs), and consequences of faster algorithms for circuit complexity. We show that satisfiability of quantified 3-CNFs with m clauses, n variables, and two quantifier blocks (one existential block and one universal) can be solved deterministically in time. poly( m ). For the case of multiple quantifier blocks (alternations), we show that satisfiability of quantified CNFs of size poly( n ) on n variables with q quantifier blocks can be solved in 2 n−n 1/( q + 1) · poly( n ) time by a zero-error randomized algorithm. These are the first provable improvements over brute force search in the general case, even for quantified polynomial-sized CNFs with two quantifier blocks. A second zero-error randomized algorithm solves QBF on circuits of size s in 2 n– Ω( q ) · poly( s ) time when the number of quantifier blocks is q. We complement these algorithms by showing that improvements on them would imply new circuit complexity lower bounds. For example, if satisfiability of quantified CNF formulas with n variables, poly( n ) size and at most q quantifier blocks can be solved in time 2 n–n w q (1/ q ) then the complexity class NEXP does not have O (log n ) depth circuits of polynomial size. Furthermore, solving satisfiability of quantified CNF formulas with n variables, poly( n ) size and O (log n ) quantifier blocks in time 2 n–w (log ( n )) time would imply the same circuit complexity lower bound. The proofs of these results proceed by establishing strong relationships between the time complexity of QBF satisfiability over CNF formulas and the time complexity of QBF satisfiability over arbitrary Boolean formulas.

SAT Conference 2015 Conference Paper

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP

• Ruiwen Chen
• Rahul Santhanam

Abstract We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX- k -CSP. For instances with n variables and cn clauses (constraints), we give algorithms running in time \({{\mathrm{poly}}}(n)\cdot 2^{n(1-\mu )}\) for \(\mu = \Omega (\frac{1}{c} )\) and polynomial space solving MAX-SAT and MAX- k -SAT, \(\mu = \Omega (\frac{1}{\sqrt{c}} )\) and exponential space solving MAX-SAT and MAX- k -SAT, \(\mu = \Omega (\frac{1}{ck^2} )\) and polynomial space solving MAX- k -CSP, \(\mu = \Omega (\frac{1}{\sqrt{ck^3}} )\) and exponential space solving MAX- k -CSP. The previous MAX-SAT algorithms have savings \(\mu =\Omega (\frac{1}{c^2 \log ^2 c})\) for running in polynomial space [ 15 ] and \(\mu =\Omega (\frac{1}{c \log c})\) for exponential space [ 5 ]. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with cn wires.

I&C Journal 2013 Journal Article

Permanent does not have succinct polynomial size arithmetic circuits of constant depth

• Maurice Jansen
• Rahul Santhanam

We show that over fields of characteristic zero there does not exist a polynomial p ( n ) and a constant-free succinct arithmetic circuit family { Φ n } using division by constants, 3 where Φ n has size at most p ( n ) and depth O ( 1 ), such that Φ n computes the n × n permanent. A circuit family { Φ n } is succinct if there exists a nonuniform Boolean circuit family { C n } with O ( log n ) many inputs and size n o ( 1 ) such that C n can correctly answer direct connection language queries about Φ n – succinctness is a relaxation of uniformity. To obtain this result we develop a novel technique that further strengthens the connection between black-box derandomization of polynomial identity testing and lower bounds for arithmetic circuits. From this, we obtain the lower bound by giving an explicit construction, computable in the polynomial hierarchy, of a hitting set for arithmetic circuits.

FOCS Conference 2012 Conference Paper

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

• Arkadev Chattopadhyay
• Rahul Santhanam

We formulate a new connection between instance compressibility [1]), where the compressor uses circuits from a class C, and correlation with circuits in C. We use this connection to prove the first lower bounds on general probabilistic multi-round instance compression. We show that there is no probabilistic multi-round compression protocol for Parity in which the computationally bounded party uses a non-uniform AC 0 -circuit and transmits at most n/(log(n)) ω(1) bits. This result is tight, and strengthens results of Dubrov and Ishai. We also show that a similar lower bound holds for Majority. We also consider the question of round separation, i. e. , whether for each r ≥ 1, there are functions which can be compressed better with r rounds of compression than with r - 1 rounds. We answer this question affirmatively for compression using constant-depth polynomial-size circuits. Finally, we prove the first non-trivial lower bounds for 1-round compressibility of Parity by polynomial size ACC 0 [p] circuits where p is an odd prime.

FOCS Conference 2010 Conference Paper

Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability

• Rahul Santhanam

We investigate the possibility of finding satisfying assignments to Boolean formulae and testing validity of quantified Boolean formulae (QBF) asymptotically faster than a brute force search. Our first main result is a simple deterministic algorithm running in time 2 n-Ω(n) for satisfiability of formulae of linear size in n, where n is the number of variables in the formula. This algorithm extends to exactly counting the number of satisfying assignments, within the same time bound. Our second main result is a deterministic algorithm running in time 2 n-Ω(n/log(n)) for solving QBFs in which the number of occurrences of any variable is bounded by a constant. For instances which are "structured", in a certain precise sense, the algorithm can be modified to run in time 2 n-Ω(n). To the best of our knowledge, no non-trivial algorithms were known for these problems before. As a byproduct of the technique used to establish our first main result, we show that every function computable by linear-size formulae can be represented by decision trees of size 2 n-Ω(n). As a consequence, we get strong superlinear average-case formula size lower bounds for the Parity function.

MFCS Conference 2009 Conference Paper

Branching Programs for Tree Evaluation

• Mark Braverman
• Stephen A. Cook
• Pierre McKenzie
• Rahul Santhanam
• Dustin Wehr

Abstract The problem \(FT^{h}_{d}(k)\) consists in computing the value in [ k ] = {1, .. ., k } taken by the root of a balanced d -ary tree of height h whose internal nodes are labelled with d -ary functions on [ k ] and whose leaves are labelled with elements of [ k ]. We propose \({FT^{h}_{d}(k)}\) as a good candidate for witnessing \({\mathbf{L}} \subsetneq{\mathbf{LogDCFL}}\). We observe that the latter would follow from a proof that k -way branching programs solving \({FT^{h}_{d}(k)}\) require \(\Omega(k^{\mbox{\scriptsize unbounded function}(h)})\) size. We introduce a “state sequence” method that can match the size lower bounds on \(FT^{h}_{d}(k)\) obtained by the Nec̆iporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ( k 3 ) and Θ( k 5/2 ) for deterministic and nondeterministic branching programs solving \(FT^{3}_{2}(k)\) respectively. We propose as a challenge to break the quadratic barrier inherent in the Nec̆iporuk method by adapting the state sequence method to handle \(FT^{4}_{d}(k)\).

STOC Conference 2008 Conference Paper

Infeasibility of instance compression and succinct PCPs for NP

• Lance Fortnow
• Rahul Santhanam

The OR-SAT problem asks, given Boolean formulae Φ 1 ,...,Φ m each of size at most n, whether at least one of the Φ i 's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless NP ⊆ coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications. A number of parametric $\NP$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP ⊆ coNP/poly. Satisfiability does not have PCPs of size polynomial in the number of variables unless NP ⊆ coNP/poly. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (Buhrman-Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.

STOC Conference 2007 Conference Paper

Circuit lower bounds for Merlin-Arthur classes

• Rahul Santhanam

ICML Conference 2006 Conference Paper

Graph model selection using maximum likelihood

• Ivona Bezáková
• Adam Tauman Kalai
• Rahul Santhanam

STOC Conference 2005 Conference Paper

Hierarchies for semantic classes

• Lance Fortnow
• Rahul Santhanam
• Luca Trevisan 0001

We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n a )/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all common semantic time classes including RTIME, NTIME ∩ coNTIME, UTIME, MATIME, AMTIME and BQTIME.We show a stronger hierarchy for RTIME: For every constant c, RP/1 is not contained in RTIME(n c )/(log n) 1/2c . To prove this result we first prove a similar statement for NP by building on Zák's proof of the nondeterministic time hierarchy.

FOCS Conference 2004 Conference Paper

Hierarchy Theorems for Probabilistic Polynomial Time

• Lance Fortnow
• Rahul Santhanam

We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 /spl les/ /spl alpha/ /spl les/ /spl beta/, BPTIME(n/sup /spl alpha//)/l /spl sube/ BPTIME(n/sup /spl beta//)/l. This result builds on and improves an earlier hierarchy of Barak using O(log log n) bits of advice. We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME (n/sup d/). We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probabilistic algorithms for L take only slightly more time than average-case algorithms.