research
∙
05/24/2023
Polynomial-Time Pseudodeterministic Construction of Primes
A randomized algorithm for a search problem is *pseudodeterministic* if ...
share
research
∙
03/27/2022
Constructive Separations and Their Consequences
For a complexity class C and language L, a constructive separation of L ...
research
∙
12/28/2021
Quantum Merkle Trees
Commitment scheme is a central task in cryptography, where a party (typi...
research
∙
11/02/2021
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
We consider low-space algorithms for the classic Element Distinctness pr...
research
∙
02/22/2021
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
For a directed graph G with n vertices and a start vertex u_ start, we w...
research
∙
09/21/2020
On Distributed Differential Privacy and Counting Distinct Elements
We study the setup where each of n users holds an element from a discret...
research
∙
11/19/2019
Beyond Natural Proofs: Hardness Magnification and Locality
Hardness magnification reduces major complexity separations (such as EXP...
research
∙
05/19/2019
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
We develop techniques to prove lower bounds for the BCAST(log n) Broadca...
research
∙
11/29/2018
An Equivalence Class for Orthogonal Vectors
The Orthogonal Vectors problem (OV) asks: given n vectors in {0,1}^O( n)...
research
∙
11/19/2018
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
The polynomial method from circuit complexity has been applied to severa...
research
∙
05/27/2018
Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits
Proving super-polynomial size lower bounds for TC^0, the class of consta...
research
∙
05/07/2018
Fine-grained Complexity Meets IP = PSPACE
In this paper we study the fine-grained complexity of finding exact and ...
research
∙
04/18/2018
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Since the introduction of retroactive data structures at SODA 2004, a ma...
research
∙
02/07/2018
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
In this paper we study the (Bichromatic) Maximum Inner Product Problem (...
research
∙
06/04/2017
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
We study the combinatorial pure exploration problem Best-Set in stochast...
research
∙
02/13/2017
Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
In the Best-k-Arm problem, we are given n stochastic bandit arms, each a...
research
∙
08/22/2016
