Explanipedia

Lower bounds on the complexity of mixed-integer programs for stable set and knapsack Open

Jamico Schade, Makrand Sinha, Stefan Weltge · 2025

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 formulat…

The Hardness of Learning Quantum Circuits and its Cryptographic Applications Open

Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen · 2025

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one…

The Power of Adaptivity in Quantum Query Algorithms Open

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu · 2024

Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to th…

Simple constructions of linear-depth t-designs and pseudorandom unitaries Open

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen · 2024

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that "look" sufficiently Haar rand…

Pseudorandom unitaries with non-adaptive security Open

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen · 2024

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 simp…

The Power of Adaptivity in Quantum Query Algorithms Open

Uma Girish, Makrand Sinha, Avishay Ta, Kewen Wu · 2023

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 t…

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack Open

Jamico Schade, Makrand Sinha, Stefan Weltge · 2023

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 form…

Fourier Growth of Communication Protocols for XOR Functions Open

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu · 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 …

Quantum Cryptography in Algorithmica Open

William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal · 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 sho…

Quantum Cryptography in Algorithmica Open

William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal · 2022

We construct a classical oracle relative to which $\mathsf{P} = \mathsf{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 "Algorith…

The NISQ Complexity of Collision Finding Open

Yassine Hamoudi, Qipeng Liu, Makrand Sinha · 2022

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 app…

Smoothed Analysis of the Komlós Conjecture Open

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha · 2022

The well-known Komlós 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 …

Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms Open

Nikhil Bansal, Makrand Sinha, Ronald de Wolf · 2022

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 $…

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing Open

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha · 2022

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 ℝ^d, find ± signs for each of them such that the signed sum ve…

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector\n Balancing Open

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha · 2021

A well-known result of Banaszczyk in discrepancy theory concerns the prefix\ndiscrepancy problem (also known as the signed series problem): given a sequence\nof $T$ unit vectors in $\\mathbb{R}^d$, find $\\pm$ signs for each of them such\n…

k-forrelation optimally separates Quantum and classical query complexity Open

Nikhil Bansal, Makrand Sinha · 2021

Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$ bits that can be computed with an advantage $δ$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $δ/2$ by a ran…

Online Discrepancy Minimization for Stochastic Arrivals Open

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha · 2021

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 nor…

Majorizing Measures for the Optimizer Open

Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha · 2021

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 q…

Majorizing Measures for the Optimizer Open

Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha · 2020

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 q…

Edge Estimation with Independent Set Oracles Open

Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha · 2020

We study the task of estimating the number of edges in a graph, where the access to the graph is provided via an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of …

Online vector balancing and geometric discrepancy Open

Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha · 2020

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 small as possible. …

Exponential Separation between Quantum Communication and Logarithm of\n Approximate Rank Open

Makrand Sinha, de Wolf Ronald · 2018

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total\nBoolean function, the sink function, that has polynomial approximate rank and\npolynomial randomized communication complexity. This gives an exponential\nseparation be…

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank Open

Makrand Sinha, Ronald de Wolf · 2018

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 betwe…

Lower Bounds for Approximating the Matching Polytope Open

Makrand Sinha · 2018

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least $\binom{n}{α/{\varepsilon}}$ defining inequa…

A Direct-Sum Theorem for Read-Once Branching Programs Open

Anup Rao, Makrand Sinha · 2016

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, ..., x_n) how much memory is required to compute f on k independent inputs that arrive in…

Makrand Sinha YOU? Author Swipe