research
∙
07/04/2023
Faster Detours in Undirected Graphs
The k-Detour problem is a basic path-finding problem: given a graph G on...
share
research
∙
06/30/2022
On the Number of Quantifiers as a Complexity Measure
In 1981, Neil Immerman described a two-player game, which he called the ...
research
∙
03/27/2022
Constructive Separations and Their Consequences
For a complexity class C and language L, a constructive separation of L ...
research
∙
07/09/2021
Smaller ACC0 Circuits for Symmetric Functions
What is the power of constant-depth circuits with MOD_m gates, that can ...
research
∙
07/06/2021
MAJORITY-3SAT (and Related Problems) in Polynomial Time
Majority-SAT is the problem of determining whether an input n-variable f...
research
∙
11/07/2020
Fast Low-Space Algorithms for Subset Sum
We consider the canonical Subset Sum problem: given a list of positive i...
research
∙
01/21/2020
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
We continue the program of proving circuit lower bounds via circuit sati...
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
∙
12/21/2017
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Fine-grained reductions have established equivalences between many core ...
research
∙
09/15/2017
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
In the Orthogonal Vectors (OV) problem, we wish to determine if there is...
research
∙
09/15/2017
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry
Point location problems for n points in d-dimensional Euclidean space (a...
research
∙
11/24/2015
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
In order to formally understand the power of neural computing, we first ...
research
∙
10/30/2012
An Atypical Survey of Typical-Case Heuristic Algorithms
Heuristic approaches often do so well that they seem to pretty much alwa...
research
∙
01/05/2010