Thomas M. Siebel Center for Computer Science
201 North Goodwin Avenue
Urbana, IL 61801-2302
Email: msinha @ followed by illinois edu separated by dots
About Me
I am an assistant professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign.
Previously I was a Simons-Berkeley postdoctoral fellow at the Simons Institute at UC Berkeley and a postdoctoral researcher in the Networks and Optimization group at CWI in Amsterdam.
My research is in the area of theoretical computer science. My primary research interests lie in the foundations of quantum and classical computation and optimization, and specifically in understanding the relative power of quantum vs classical algorithms and communication protocols, understanding limitations of various approaches in optimization such as Linear or Semidefinite Programs, and designing algorithms for various optimization problems.
Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of \(U^{\otimes \mathrm{poly}(n)}\) can distinguish whether an \(n\)-qubit unitary \(U\) was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.
The Power of Adaptivity in Quantum Query Algorithms Uma Girish, Makrand Sinha, Avishay Tal and Kewen Wu
To appear in STOC 2024.
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with \(r\) versus \(r−1\) rounds of adaptivity. We do so by using the \(k\)-fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP'18). For \(k=2r\), this problem can be solved using an \(r\) round quantum algorithm with only one query per round, yet we show that any \(r−1\) round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round.
Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.
The NISQ Complexity of Collision Finding Yassine Hamoudi, Qipeng Liu and Makrand Sinha
To appear in Eurocrypt 2024.
Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. The complexity of this problem is well-understood in the classical setting and \(\Theta(N^{1/2})\) queries are needed to find a collision. However, the advent of quantum computing has introduced new challenges since quantum adversaries --- equipped with the power of quantum queries --- can find collisions much more efficiently. Brassard, Høyer and Tapp and Aaronson and Shi established that full-scale quantum adversaries require \(\Theta(N^{1/3})\) queries to find a collision, prompting a need for longer hash outputs, which impacts efficiency in terms of the key lengths needed for security.
This paper explores the implications of quantum attacks in the Noisy-Intermediate Scale Quantum (NISQ) era. In this work, we investigate three different models for NISQ algorithms and achieve tight bounds for all of them:
A hybrid algorithm making adaptive quantum or classical queries but with a limited quantum query budget, or
quantum algorithm with access to a noisy oracle, or
hybrid algorithm with an upper bound on its maximum quantum depth; i.e. a classical algorithm aided by low-depth quantum circuits.
Previously, only results for the preimage search problem were known for these models (by Sun and Zheng; Rosmanis; Chen, Cotler, Huang and Li) while nothing was known about the collision finding problem.
Along with our main results, we develop an information-theoretic framework for recording query transcripts of quantum-classical algorithms. The main feature of this framework is that it allows us to record queries in two incompatible bases --- classical queries in the standard basis and quantum queries in the Fourier basis --- consistently. We call the framework the hybrid compressed oracle as it naturally interpolates between the classical way of recording queries and the compressed oracle framework of Zhandry for recording quantum queries. We demonstrate its applicability by giving simpler proofs of the optimal lower bounds for NISQ preimage search and by showing optimal lower bounds for NISQ collision finding.
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
Jamico Schade, Makrand Sinha and Stefan Weltge
To appear in IPCO 2024.
Standard mixed-integer programming formulations for the stable set problem on \(n\)-node graphs require n integer variables. We prove that this is almost optimal: We give a family of \(n\)-node graphs for which every polynomial-size MIP formulation requires \(\Omega(n/\log^2 n)\) integer variables. By a polyhedral reduction we obtain an analogous result for \(n\)-item knapsack problems. In both cases, this improves the previously known bounds of \(\Omega(\sqrt{n}/\log n)\) by Cevallos, Weltge and Zenklusen (SODA 2018).
To this end, we show that there exists a family of \(n\)-node graphs whose stable set polytopes satisfy the following: any \((1+\epsilon/n)\)-approximate extended formulation for these polytopes, for some constant \(\epsilon>0\), has size \(2^{\Omega(n/\log n)}\). Our proof extends and simplifies the information-theoretic methods due to Göös, Jain and Watson (FOCS 2016, SIAM J. Comput. 2018) who showed the same result for the case of exact extended formulations (i.e. \(\epsilon =0)\).
Fourier Growth of Communication Protocols for XOR Functions Uma Girish, Makrand Sinha, Avishay Tal and Kewen Wu
Appeared in FOCS 2023.
The level-\(k\) \(\ell_1\)-Fourier weight of a Boolean function refers to the sum of absolute values of its level-\(k\) Fourier coefficients. Fourier growth refers to the growth of these weights as \(k\) grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.
In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs \(x\) and \(y\) to Alice and Bob). If a protocol \(\mathcal{C}\) computes an XOR function, then \(\mathcal{C}(x, y)\) is a function of the parity \(x \oplus y\). This motivates us to analyze the XOR-fiber of the communication protocol \(\mathcal{C}\), defined as \(h(z) := \mathbb{E}_{x,y}[\mathcal{C}(x, y) | x\oplus y = z]\).
We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate \(d\) bits. For the first level, we show a tight \(O(\sqrt{d})\) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an \(d^{3/2} \cdot \mathrm{polylog}(n)\) bound, which improves the previous \(O(d^2)\) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.
Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.
Quantum Cryptography in Algorithmica William Kretschmer, Luowen Qian, Makrand Sinha and Avishay Tal
Appeared in STOC 2023. Contributed Talk at QIP 2023. Invited Talk at QCrypt 2023.
We construct a classical oracle relative to which \(P = NP\) yet single-copy secure pseudorandom
quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of
pseudorandom states in “Algorithmica,” and hence shows that in a black-box setting, quantum
cryptography based on pseudorandom states is possible even if one-way functions do not exist.
As a consequence, we demonstrate that there exists a property of a cryptographic hash function
that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle,
and (3) is independent of \(P\) vs. \(NP\) in the black-box setting. We also introduce a conjecture
that would generalize our results to multi-copy secure pseudorandom states.
We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an
oracle relative to which \(P = NP\) yet \(BQP \neq QCMA\), based on hardness of the OR \(\circ\) Forrelation
problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution,
for which we prove pseudorandomness against \(AC0\) circuits. This variant may be of independent
interest.
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms Nikhil Bansal, Makrand Sinha and Ronald de Wolf
In proceedings of CCC 2022. Contributed Talk at QIP 2023.
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every \(d\)-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a \(\mathrm{poly}(d)\)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-\(d\) block-multilinear form with constant variance, there always exists a variable with influence at least \(1/\mathrm{poly}(d)\). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Brïet and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance \(k\)-fold Forrelation. Our main technical result relies on connections to free probability theory.
The well-known Komlos conjecture states that given \(n\) vectors in \(\mathbb{R}^d\) with Euclidean norm at most one, there always exists a \(\pm 1\) coloring such that the \(\ell_{\infty}\) norm of the signed-sum vector is a constant independent of \(n\) and \(d\). We prove this conjecture in a smoothed analysis setting where the vectors are perturbed by adding a small Gaussian noise and when the number of vectors \(n =\omega(d\log d)\). The dependence of \(n\) on \(d\) is the best possible even in a completely random setting.
Our proof relies on a weighted second moment method, where instead of considering uniformly randomly colorings we apply the second moment method on an implicit distribution on colorings obtained by applying the Gram-Schmidt walk algorithm to a suitable set of vectors. The main technical idea is to use various properties of these colorings, including subgaussianity, to control the second moment.
A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of \(T\) unit vectors in \(\mathbb{R}^d\), find \(\pm\) signs for each of them such that the signed sum vector along any prefix has a small \(\ell_\infty\)-norm? This problem is central to proving upper bounds for the Steinitz problem, and the popular Koml\'os problem is a special case where one is only concerned with the final signed sum vector instead of all prefixes.
Banaszczyk gave an \(O(\sqrt{\log d+ \log T})\) bound for the prefix discrepancy problem. We investigate the tightness of Banaszczyk's bound and consider natural generalizations of prefix discrepancy:
We first consider a {smoothed analysis} setting, where a small amount of additive noise perturbs the input vectors. We show an exponential improvement in \(T\) compared to Banaszczyk's bound. Using a primal-dual approach and a careful chaining argument, we show that one can achieve a bound of \(O(\sqrt{\log d+ \log\!\log T})\) with high probability in the smoothed setting. Moreover, this smoothed analysis bound is the best possible without further improvement on Banaszczyk's bound in the worst case.
We also introduce a generalization of the prefix discrepancy problem to arbitrary DAGs. Here, vertices correspond to unit vectors, and the discrepancy constraints correspond to paths on a DAG on \(T\) vertices --- prefix discrepancy is precisely captured when the DAG is a simple path. We show that an analog of Banaszczyk's \(O(\sqrt{\log d+ \log T})\) bound continues to hold in this setting for adversarially given unit vectors and that the \(\sqrt{\log T}\) factor is unavoidable for DAGs. We also show that unlike for prefix discrepancy, the dependence on \(T\) cannot be improved significantly in the smoothed case for DAGs.
We conclude by exploring a more general notion of vector balancing, which we call combinatorial vector balancing. In this problem, the discrepancy constraints are generalized from paths of a DAG to an arbitrary set system. We obtain near-optimal bounds in this setting, up to poly-logarithmic factors.
\(k\)-Forrelation Optimally Separates Quantum and Classical Query Complexity Nikhil Bansal and Makrand Sinha
Appeared in STOC '21. Contributed Talk at QIP '21.
Aaronson and Ambainis (SICOMP `18) showed that any partial function on \(N\) bits that can be computed with an advantage \(\delta\) over a random guess by making \(q\) quantum queries, can also be computed classically with an advantage \(\delta/2\) by a randomized decision tree making \({O}_q(N^{1-\frac{1}{2q}}\delta^{-2})\) queries. Moreover, they conjectured the \(k\)-Forrelation problem --- a partial function that can be computed with \(q = \lceil k/2 \rceil\) quantum queries --- to be a suitable candidate for exhibiting such an extremal separation.
We prove their conjecture by showing a tight lower bound of \(\widetilde{\Omega}(N^{1-1/k})\) for the randomized query complexity of \(k\)-Forrelation, where the advantage \(\delta = 2^{-O(k)}\). By standard amplification arguments, this gives an explicit partial function that exhibits an \(O_\epsilon(1)\) vs \(\Omega(N^{1-\epsilon})\) separation between bounded-error quantum and randomized query complexities, where \(\epsilon>0\) can be made arbitrarily small. Our proof also gives the same bound for the closely related but non-explicit \(k\)-Rorrelation function introduced by Tal (FOCS `20).
Our techniques rely on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, give a more general statement. We show that to prove lower bounds for \(k\)-Forrelation against a family of functions, it suffices to bound the \(\ell_1\)-weight of the Fourier coefficients between levels \(k\) and \((k-1)k\). We also prove new interpolation and integration by parts identities that might be of independent interest in the context of rounding high-dimensional Gaussian vectors.
Majorizing Measures for the Optimizer
Sander Borst, Daniel Dadush, Neil Olver and Makrand Sinha
Appeared in ITCS '21.
The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochastic processes. In particular, it can be applied to derive quantitative bounds on the expected suprema and the degree of continuity of sample paths for many processes.
One of the crowning achievements of the theory is Talagrand’s tight alternative characterization of the suprema of Gaussian processes in terms of majorizing measures. The proof of this theorem was difficult, and thus considerable effort was put into the task of developing both shorter and easier to understand proofs. A major reason for this difficulty was considered to be theory of majorizing measures itself, which had the reputation of being opaque and mysterious. As a consequence, most recent treatments of the theory (including by Talagrand himself) have eschewed the use of majorizing measures in favor of a purely combinatorial approach (the generic chaining) where objects based on sequences of partitions provide roughly matching upper and lower bounds on the desired expected supremum.
In this paper, we return to majorizing measures as a primary object of study, and give a viewpoint that we think is very natural and clarifying from an optimization perspective. As our main contribution, we give an algorithmic proof of the majorizing measures theorem based on two parts:
- We make the simple (but apparently new) observation that finding the best majorizing measure can be cast as a convex program. This also allows for efficiently computing the measure using off-the-shelf methods from convex optimization.
- We obtain tree-based upper and lower bound certificates by rounding, in a series of steps, the primal and dual solutions to this convex program.
While duality has conceptually been part of the theory since its beginnings, as far as we are aware no explicit link to convex optimization has been previously made.
In the stochastic online vector balancing problem, vectors \(v_1,v_2,\ldots,v_T\) chosen independently from an arbitrary distribution in \(\mathbb{R}^n\) arrive one-by-one and must be immediately given a \(\pm\) sign. The goal is to keep the norm of the discrepancy vector, i.e., the signed prefix-sum, as small as possible for a given target norm.
We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to \(\mathrm{polylog}(nT)\) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Komóls problem where \(\|v_t\|_2\leq 1\) for each \(t\), our algorithm achieves \(\widetilde{O}(1)\) discrepancy with high probability, improving upon the previous \(\widetilde{O}(n^{3/2})\) bound. For Tusnády's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an \(O(\log^{d+4} T)\) bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker \(O(\log^{2d+1} T)\) bound. We also consider the Banaszczyk setting, where given a symmetric convex body \(K\) with Gaussian measure at least \(1/2\), our algorithm achieves \(\widetilde{O}(1)\) discrepancy with respect to the norm given by \(K\) for input distributions with sub-exponential tails.
Our results are based on a new potential function approach. Previous techniques consider a potential that penalizes large discrepancy, and greedily chooses the next color to minimize the increase in potential. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. We believe that our techniques to control the evolution of states could find other applications in stochastic processes and online algorithms. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multi-color discrepancy.
Online Vector Balancing and Geometric Discrepancy Nikhil Bansal, Haotian Jiang, Sahil Singla and Makrand Sinha
Appeared in STOC '20. Invited talk at TCS+.
We consider an {online vector balancing} question where \(T\) vectors, chosen from an {arbitrary} distribution over \([-1,1]^n\), arrive one-by-one and must be immediately given a \(\pm\) sign. The goal is to keep the {discrepancy}---the \(\ell_{\infty}\)-norm of any signed prefix-sum---as small as possible. A concrete example of this question is the {online interval discrepancy} problem where \(T\) points are sampled one-by-one uniformly in the unit interval \([0,1]\), and the goal is to immediately color them \(\pm\) such that every sub-interval remains always nearly balanced. As random coloring incurs \(\Omega(T^{1/2})\) discrepancy, while the offline bounds are \(\Theta((n\log T)^{1/2})\) for vector balancing and \(1\) for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is \(\Omega(T^{1/2})\) for any online algorithm.
In a special case of online vector balancing, Bansal and Spencer (arXiv '19)} recently show an \(O(\sqrt{n}\log T)\) bound when each coordinate is independently chosen. When there are dependencies among the coordinates, as in the interval discrepancy problem, the problem becomes much more challenging, as evidenced by a recent work of Jiang, Kulkarni, and Singla (arXiv '19) that gives a non-trivial \(O(T^{1/\log\log T})\) bound for online interval discrepancy. Although this beats random coloring, it is still far from the offline bound.
In this work, we introduce a new framework that allows us to handle online vector balancing even when the input distribution has {dependencies} across coordinates. In particular, this lets us obtain a \(\mathrm{poly}(n, \log T)\) bound for online vector balancing under arbitrary input distributions, and a \(\mathrm{polylog} (T)\) bound for online interval discrepancy. Our framework is powerful enough to capture other well-studied geometric discrepancy problems; e.g., we obtain a \(\mathrm{poly}(\log^d (T))\) bound for the online \(d\)-dimensional Tusnády's problem. All our bounds are tight up to polynomial factors.
A key new technical ingredient in our work is an anti-concentration inequality for sums of pairwise uncorrelated random variables, which might also be of independent interest.
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Makrand Sinha and Ronald de Wolf
Appeared in FOCS '19. Contributed talk at QIP '20 (as part of a joint submission).
Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture.
Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (ECCC 2015) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method.
Simplified Separation of Information and Communication Anup Rao and Makrand Sinha
Appeared in Theory of Computing, 2018.
We give an example of a boolean function whose information complexity is exponentially smaller than its communication complexity. This was first proven recently by Ganor, Kol and Raz (J. ACM 2016) and our work gives a simpler proof of the same result. In the course of this simplification, we make several new contributions: we introduce a new communication lower bound technique, the notion of a fooling distribution, which allows us to separate information and communication complexity, and we also give a more direct proof for the information complexity upper bound.
We also prove a generalization of Shearer's Lemma that may be of independent interest. A version of Shearer's original lemma bounds the expected mutual information of a subset of random variables with another random variable, when the subset is chosen independently of all the random variables that are involved. Our generalization allows some dependence between the random subset and the random variables involved, and still gives us similar bounds with an appropriate error term.
We study the problem of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an \(n\)-vertex graph: one that uses only \(\mathrm{polylog}(n)\) bipartite independent set queries, and another one that uses \({n}^{2/3} \cdot \mathrm{polylog}(n)\) independent set queries.
Lower Bounds for Approximating the Matching Polytope
Makrand Sinha
Appeared in SODA '18. Invited talk at ISMP '18.
We prove that any extended formulation that approximates the matching polytope on \(n\)-vertex graphs up to a factor of \((1+\epsilon)\) for any \(\frac2n \le \epsilon \le 1\) must have at least \({n} \choose {{\alpha}/{\epsilon}}\) defining inequalities where \(0<\alpha<1\) is an absolute constant. This is tight as exhibited by the \((1+\epsilon)\) approximating linear program obtained by dropping the odd set constraints of size larger than \(({1+\epsilon})/{\epsilon}\) from the description of the matching polytope. Previously, a tight lower bound of \(2^{\Omega(n)}\) was only known for \(\epsilon = O\left(\frac{1}{n}\right)\) [Rothvoss, STOC '14; Braun and Pokutta, IEEE Trans. Information Theory '15] whereas for \(\frac2n \le \epsilon \le 1\), the best lower bound was \(2^{\Omega\left({1}/{\epsilon}\right)}\) [Rothvoss, STOC '14]. The key new ingredient in our proof is a close connection to the non-negative rank of a lopsided version of the unique disjointness matrix.
A Direct-sum Theorem for Read-Once Branching Programs Anup Rao and Makrand Sinha
Appeared in RANDOM '16.
We study a direct-sum question for read-once branching programs. If \(M(f)\) denotes the minimum average memory required to compute a function \(f(x_1,x_2, \dotsc, x_n)\) how much memory is required to compute \(f\) on \(k\) independent inputs that arrive in parallel? We show that when the inputs (updates) are sampled independently from some domain \(\mathcal{X}\) and \(M(f) = \Omega(n)\), then computing the value of \(f\) on \(k\) streams requires average memory at least \(\Omega\left(k \cdot \frac{M(f)}{n}\right)\).
Our results are obtained by defining new ways to measure the information complexity of read-once branching programs. We define two such measures: the transitional and cumulative information content. We prove that any read-once branching program with transitional information content \(\mathtt{I}\) can be simulated using average memory \(\mathcal{O}(n(\mathtt{I}+1))\). On the other hand, if every read-once branching program with cumulative information content \(\mathtt{I}\) can be simulated with average memory \(\mathcal{O}(\mathtt{I}+1)\), then computing \(f\) on \(k\) inputs requires average memory at least \(\Omega(k \cdot (M(f)-1))\).
Fooling Pairs in Randomized Communication Complexity Shay Moran, Makrand Sinha and Amir Yehudayoff
Appeared in SIROCCO '16.
Fooling pairs are one of the standard methods for proving lower
bounds for deterministic two-player communication complexity.
We study fooling pairs in the context of randomized communication complexity.
We show that every fooling pair induces far away distributions
on transcripts of private-coin protocols.
We then conclude that the private-coin randomized \(\varepsilon\)-error
communication complexity of a function \(f\) with a fooling set
\(\mathcal{S}\) is at least order \(\log \frac{\log |\mathcal{S}|}{\varepsilon}\).
This is tight, for example, for the equality
and greater-than functions.
We give a simple information theoretic proof that the public-coin randomized communication
complexity of the greater-than function is \(\Omega(\log n)\) for bit-strings of length \(n\).
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Thomas Holenstein and Makrand Sinha
In proceedings of FOCS '12.
We show that a black-box construction of a pseudorandom generator from a one-way function needs to make \(\Omega(n/log(n))\) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Goldreich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses \(\mathcal{O}(n/log(n))\) calls.
Vertices of Degree \(k\) in Random Unlabeled Trees Konstantinos Panagiotou and Makrand Sinha
In proceedings of EuroComb '09. Full version appeared in Journal of Graph Theory, 2012.
Let \(\mathcal{H}_n\) be the class of unlabeled trees with \(n\) vertices, and denote by \(\mathcal{H}_n\) a tree that is drawn uniformly at random from this set. The asymptotic behavior of the random variable \(\deg_k(\mathcal{H}_n)\) that counts vertices of degree \(k\) in \(\mathcal{H}_n\) was studied, among others, by Drmota and Gittenberger, who showed that this quantity satisfies a central limit theorem. This result provides a very precise characterization of the ``central region'' of the distribution, but does not give any non-trivial information about its tails.
In this work we study further the number of vertices of degree \(k\) in \(\mathcal{H}_n\). In particular, for \(k = \mathcal{O}\left(\sqrt{\frac{\log n}{\log\log n}}\right)\) we show exponential-type bounds for the probability that \(\deg_k(\mathcal{H}_n)\) deviates from its expectation. On the technical side, our proofs are based on the analysis of a randomized algorithm that generates unlabeled trees in the so-called Boltzmann model. The analysis of such algorithms is quite well-understood for classes of labeled graphs, see e.g. the work by Bernasconi, the first author, and Steger. Comparable algorithms for unlabeled classes are unfortunately much more complex. We demonstrate in this work that they can be analyzed very precisely for classes of
unlabeled graphs as well.
Organized Workshops
Together with Ankit Garg, Raghu Meka and Tonian Pitassi, I organized a workshop on extension complexity and lifting theorems at FSTTCS '19. See here for details.
