6 papers
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…