Source author record

Rahul Santhanam

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Cryptography and Security Discrete Mathematics Machine Learning math.CO math.NT Social and Information Networks

Catalog footprint

Research overview

5works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup lemma, equivalences between various learning models in the exponential time and subexponential time regimes, a dichotomy between learning and pseudorandomness, consequences of non-trivial learning for circuit lower bounds, Karp-Lipton theorems for probabilistic exponential time, and NC $^1$ -hardness for the Minimum Circuit Size Problem.

preprint2016arXiv

Pseudodeterministic Constructions in Subexponential Time

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\}_{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 $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 much more general theorem about pseudodeterministic constructions. A property $Q \subseteq \{0,1\}^{*}$ is $γ$ -dense if for large enough $n$ , $|Q \cap \{0,1\}^n| \geq γ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 \subseteq \{0,1\}^n$ , such that for each $(1/n^c)$ -dense property $Q \in \mathsf{DTIME}(n^c)$ and every large enough $n$ , $H_n \cap Q \neq \emptyset$ ; or (2) There is a deterministic sub-exponential time construction of a family $\{H'_n\}$ of sets, $H'_n \subseteq \{0,1\}^n$ , such that for each $(1/n^c)$ -dense property $Q \in \mathsf{DTIME}(n^c)$ and for infinitely many values of $n$ , $H'_n \cap Q \neq \emptyset$ . 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.

preprint2012arXiv

Macroscopes: models for collective decision making

We introduce a new model of collective decision making, when a global decision needs to be made but the parties only possess partial information, and are unwilling (or unable) to first create a globalcomposite of their local views. Our macroscope model captures two key features of many real-world problems: allotment structure (how access to local information is apportioned between parties, including overlaps between the parties) and the possible presence of meta-information (what each party knows about the allotment structure of the overall problem). Using the framework of communication complexity, we formalize the efficient solution of a macroscope. We present general results about the macroscope model, and also results that abstract the essential computational operations underpinning practical applications, including in financial markets and decentralized sensor networks. We illustrate the computational problem inherent in real-world collective decision making processes using results for specific functions, involving detecting a change in state (constant and step functions), and computing statistical properties (the mean).

preprint2010arXiv

Pebbles and Branching Programs for Tree Evaluation

We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root. We show that the standard black pebbling algorithm applied to the binary tree of height h yields a deterministic k-way branching program with Theta(k^h) states solving this problem, and we prove that this upper bound is tight for h=2 and h=3. We introduce a simple semantic restriction called "thrifty" on k-way branching programs solving tree evaluation problems and show that the same state bound of Theta(k^h) is tight (up to a constant factor) for all h >= 2 for deterministic thrifty programs. We introduce fractional pebbling for trees and show that this yields nondeterministic thrifty programs with Theta(k^{h/2+1}) states solving the Boolean problem "determine whether the root has value 1". We prove that this bound is tight for h=2,3,4, and tight for unrestricted nondeterministic k-way branching programs for h=2,3.

preprint2010arXiv

Robust Simulations and Significant Separations

We define and study 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. There is a significant separation of L from C if there is no robust simulation of L in C. The new notion of simulation is a cleaner and more natural notion of simulation than the infinitely-often notion. 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, such as hierarchy theorems, fixed polynomial circuit lower bounds, time-space tradeoffs, and the theorems of Allender and Williams, 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.

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.