4 papers
Optimality of Linear Sketching under Modular Updates
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in dimensions, the existence of ef…
A Method for Quickly Bounding the Optimal Objective Value of an OPF Problem using a Semidefinite Relaxation and a Local Solution
Alireza Barzegar, Daniel K. Molzahn, Rong Su
Optimal power flow (OPF) is an important problem in the operation of electric power systems. Due to the OPF problem's non-convexity, there may exist multiple local optima. Certifia…
Torus polynomials: an algebraic approach to ACC lower bounds
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett +1
We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based app…
On the structure of the spectrum of small sets
Kaave Hosseini, Shachar Lovett
Let be a finite abelian group and a subset of . The spectrum of is the set of its large Fourier coefficients. Known combinatorial results on the structure of spectru…