All reports by Author Rahul Santhanam:

__
TR23-076
| 24th May 2023
__

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam#### Polynomial-Time Pseudodeterministic Construction of Primes

__
TR23-028
| 15th March 2023
__

Rahul Santhanam#### An Algorithmic Approach to Uniform Lower Bounds

__
TR22-074
| 20th May 2022
__

Michael Saks, Rahul Santhanam#### On Randomized Reductions to the Random Strings

__
TR22-048
| 4th April 2022
__

Hanlin Ren, Rahul Santhanam, Zhikun Wang#### On the Range Avoidance Problem for Circuits

__
TR21-173
| 5th December 2021
__

Ninad Rajgopal, Rahul Santhanam#### On the Structure of Learnability beyond P/poly

__
TR21-089
| 25th June 2021
__

Hanlin Ren, Rahul Santhanam#### A Relativization Perspective on Meta-Complexity

__
TR21-082
| 16th June 2021
__

Rahul Ilango, Hanlin Ren, Rahul Santhanam#### Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

__
TR21-057
| 23rd April 2021
__

Hanlin Ren, Rahul Santhanam#### Hardness of KT Characterizes Parallel Cryptography

Revisions: 1

__
TR19-168
| 20th November 2019
__

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam#### Beyond Natural Proofs: Hardness Magnification and Locality

__
TR19-155
| 6th November 2019
__

Rahul Santhanam#### Pseudorandomness and the Minimum Circuit Size Problem

__
TR19-073
| 17th May 2019
__

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan#### Parity helps to compute Majority

__
TR18-159
| 11th September 2018
__

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell#### Expander-Based Cryptography Meets Natural Proofs

Revisions: 2

__
TR18-158
| 11th September 2018
__

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam#### Hardness magnification near state-of-the-art lower bounds

Revisions: 1

__
TR18-139
| 10th August 2018
__

Igor Carboni Oliveira, Rahul Santhanam#### Hardness Magnification for Natural Problems

__
TR18-122
| 3rd July 2018
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudo-derandomizing learning and approximation

__
TR18-030
| 9th February 2018
__

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam#### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

__
TR17-173
| 6th November 2017
__

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam#### An Average-Case Lower Bound against ACC^0

__
TR16-197
| 7th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

__
TR16-196
| 5th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Constructions in Subexponential Time

__
TR15-192
| 26th November 2015
__

Ruiwen Chen, Rahul Santhanam#### Satisfiability on Mixed Instances

__
TR15-191
| 26th November 2015
__

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan#### Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

__
TR15-112
| 16th July 2015
__

Ruiwen Chen, Rahul Santhanam#### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

__
TR14-173
| 13th December 2014
__

Igor Carboni Oliveira, Rahul Santhanam#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

__
TR14-171
| 11th December 2014
__

Lance Fortnow, Rahul Santhanam#### Hierarchies Against Sublinear Advice

__
TR13-108
| 9th August 2013
__

Rahul Santhanam, Ryan Williams#### New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

__
TR12-108
| 4th September 2012
__

Arkadev Chattopadhyay, Rahul Santhanam#### Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

__
TR12-084
| 3rd July 2012
__

Rahul Santhanam#### Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds

__
TR12-077
| 10th June 2012
__

Chiranjit Chakraborty, Rahul Santhanam#### Instance Compression for the Polynomial Hierarchy and Beyond

Comments: 2

__
TR12-059
| 14th May 2012
__

Rahul Santhanam, Ryan Williams#### Uniform Circuits, Lower Bounds, and QBF Algorithms

__
TR11-135
| 9th October 2011
__

Maurice Jansen, Rahul Santhanam#### Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

__
TR11-133
| 4th October 2011
__

Maurice Jansen, Rahul Santhanam#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

__
TR11-131
| 29th September 2011
__

Rahul Santhanam, Srikanth Srinivasan#### On the Limits of Sparsification

__
TR09-064
| 3rd August 2009
__

Harry Buhrman, Lance Fortnow, Rahul Santhanam#### Unconditional Lower Bounds against Advice

__
TR07-096
| 8th October 2007
__

Lance Fortnow, Rahul Santhanam#### Infeasibility of Instance Compression and Succinct PCPs for NP

__
TR07-005
| 17th January 2007
__

Rahul Santhanam#### Circuit Lower Bounds for Merlin-Arthur Classes

__
TR07-004
| 12th January 2007
__

Lance Fortnow, Rahul Santhanam#### Time Hierarchies: A Survey

__
TR06-157
| 14th December 2006
__

Lance Fortnow, Rahul Santhanam#### Fixed-Polynomial Size Circuit Bounds

__
TR06-154
| 13th December 2006
__

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam#### Uniform Hardness Amplification in NP via Monotone Codes

__
TR06-003
| 8th January 2006
__

Joshua Buresh-Oppenheim, Rahul Santhanam#### Making Hard Problems Harder

__
TR04-098
| 5th November 2004
__

Lance Fortnow, Rahul Santhanam, Luca Trevisan#### Promise Hierarchies

__
TR02-038
| 5th June 2002
__

Rahul Santhanam#### Resource Tradeoffs and Derandomization

Revisions: 1

__
TR01-022
| 15th February 2001
__

Rahul Santhanam#### On segregators, separators and time versus space

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, 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 posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>Rahul Santhanam

We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as ``NP is not in uniform ACC^0" and ``NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our ... more >>>

Michael Saks, Rahul Santhanam

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

Hanlin Ren, Rahul Santhanam, Zhikun Wang

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

Ninad Rajgopal, Rahul Santhanam

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and EXP/poly. We show the following:

1. (Unconditional Lower Bounds for Learning) Building on [KKO13], we prove unconditionally that BPE/poly cannot be weakly ... more >>>

Hanlin Ren, Rahul Santhanam

Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:

* MCSP can be solved in deterministic polynomial time, but ... more >>>

Rahul Ilango, Hanlin Ren, Rahul Santhanam

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Hanlin Ren, Rahul Santhanam

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity K^t is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:

1. We show, perhaps surprisingly, that the ... more >>>

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

Rahul Santhanam

We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[$s$]), which asks whether a Boolean function on $n$ bits specified by its truth table has circuits of size $s(n)$.

1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for ... more >>>

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$ circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can ... more >>>

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... more >>>

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs ... more >>>

Igor Carboni Oliveira, 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$[s]$ be the decision problem whose YES instances are ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser

[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed

output with high probability. We explore pseudo-determinism in the settings of learning and ap-

proximation. Our goal is to simulate known randomized algorithms in these settings ...
more >>>

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

Ruiwen Chen, Rahul Santhanam

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most

n^{1+\epsilon_d} ...
more >>>

Ruiwen Chen, Rahul Santhanam

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 $\poly(n)\cdot 2^{n(1-\mu)}$ for

\begin{itemize}

\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,

\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and ...
more >>>

Igor Carboni Oliveira, Rahul Santhanam

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

Lance Fortnow, Rahul Santhanam

We strengthen the non-deterministic time hierarchy theorem of

\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound

holds against sublinear advice. More formally, we show that for any constants

$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$

which is not in $\NTIME(n^c)/n^{1/d}$. ...
more >>>

Rahul Santhanam, Ryan Williams

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability

of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$

quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error

randomized algorithms. This is the first known improvement over brute force search in ...
more >>>

Arkadev Chattopadhyay, Rahul Santhanam

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), 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 ...
more >>>

Rahul Santhanam

I discuss recent progress in developing and exploiting connections between

SAT algorithms and circuit lower bounds. The centrepiece of the article is

Williams' proof that $NEXP \not \subseteq ACC^0$, which proceeds via a new

algorithm for $ACC^0$-SAT beating brute-force search. His result exploits

a formal connection from non-trivial SAT algorithms ...
more >>>

Chiranjit Chakraborty, Rahul Santhanam

We define instance compressibility for parametric problems in PH and PSPACE. We observe that

the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \Sigma_{i}^{p} with respect to W-reductions, and that analogously ... more >>>

Rahul Santhanam, Ryan Williams

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>

Maurice Jansen, Rahul Santhanam

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

Maurice Jansen, Rahul Santhanam

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.

It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ...
more >>>

Rahul Santhanam, Srikanth Srinivasan

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:

every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear

number of clauses. This lemma has subsequently played a key role in the study

of the exact complexity of the satisfiability problem. A natural question is

more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Rahul Santhanam

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

Lance Fortnow, Rahul Santhanam

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>Lance Fortnow, Rahul Santhanam

We explore whether various complexity classes can have linear or

more generally $n^k$-sized circuit families for some fixed $k$. We

show

1) The following are equivalent,

- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k

- P^NP|| is in SIZE(n^k) for some k

- ONP/1 is in ...
more >>>

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

We consider the problem of amplifying uniform average-case hardness

of languages in $\NP$, where hardness is with respect to $\BPP$

algorithms. We introduce the notion of \emph{monotone}

error-correcting codes, and show that hardness amplification for

$\NP$ is essentially equivalent to constructing efficiently

\emph{locally} encodable and \emph{locally} list-decodable monotone

codes. The ...
more >>>

Joshua Buresh-Oppenheim, Rahul Santhanam

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

Lance Fortnow, Rahul Santhanam, Luca Trevisan

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 the common

promise time classes including RTIME, NTIME \cap coNTIME, UTIME,

MATIME, AMTIME and BQTIME.

We show a ... more >>>

Rahul Santhanam

We consider uniform assumptions for derandomization. We provide

intuitive evidence that BPP can be simulated non-trivially in

deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE

implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP

= P. These results extend and complement earlier work of ...
more >>>

Rahul Santhanam

We give the first extension of the result due to Paul, Pippenger,

Szemeredi and Trotter that deterministic linear time is distinct from

nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))

\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the

following statements holds: (1) P \neq L ...
more >>>