research
∙
01/13/2023
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
Cumulative memory – the sum of space used over the steps of a computatio...
share
research
∙
11/30/2022
On Disperser/Lifting Properties of the Index and Inner-Product Functions
Query-to-communication lifting theorems, which connect the query complex...
research
∙
06/01/2019
Smoothing Structured Decomposable Circuits
We study the task of smoothing a circuit, i.e., ensuring that all childr...
research
∙
06/18/2018
On the Bias of Reed-Muller Codes over Odd Prime Fields
We study the bias of random bounded-degree polynomials over odd prime fi...
research
∙
11/20/2017
Edge Estimation with Independent Set Oracles
We study the problem of estimating the number of edges in a graph with a...
research
∙
10/09/2017
Stabbing Planes
We introduce and develop a new semi-algebraic proof system, called Stabb...
research
∙
08/08/2017
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
We develop an extension of recently developed methods for obtaining time...
research
∙
06/08/2015
New Limits for Knowledge Compilation and Applications to Exact Model Counting
We show new limits on the efficiency of using current techniques to make...
research
∙
12/03/2014
Symmetric Weighted First-Order Model Counting
The FO Model Counting problem (FOMC) is the following: given a sentence ...
research
∙
09/26/2013