50 citations · 56 across the 9 of their papers we have counts for
16 papers
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal +1
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 adapti…
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
Jamico Schade, Makrand Sinha, Stefan Weltge
Standard mixed-integer programming formulations for the stable set problem on -node graphs require integer variables. We prove that this is almost optimal: We give a family…
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha +1
We construct a classical oracle relative to which yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds,…
The NISQ Complexity of Collision Finding
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
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 p…
Smoothed Analysis of the Komlós Conjecture
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
The well-known Komlós conjecture states that given vectors in with Euclidean norm at most one, there always exists a coloring such that the $\ell_{\infty…
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
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 t…
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
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 unit vectors in $…
Majorizing Measures for the Optimizer
Sander Borst, Daniel Dadush, Neil Olver +1
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 stochas…
-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal, Makrand Sinha
Aaronson and Ambainis (SICOMP `18) showed that any partial function on bits that can be computed with an advantage over a random guess by making quantum queries, can al…
Online Discrepancy Minimization for Stochastic Arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
In the stochastic online vector balancing problem, vectors chosen independently from an arbitrary distribution in arrive one-by-one and must be…
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla +1
We consider an online vector balancing question where vectors, chosen from an arbitrary distribution over , arrive one-by-one and must be immediately given a si…
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
Makrand Sinha, Ronald de Wolf
Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communica…
Lower Bounds for Approximating the Matching Polytope
Makrand Sinha
We prove that any extended formulation that approximates the matching polytope on -vertex graphs up to a factor of for any must…
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task 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 ap…
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Thomas Holenstein, Makrand Sinha
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 hol…