20 citations · 164 across the 63 of their papers we have counts for
6 papers · 1 filter
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…
The analytic rank of tensors and its applications
Shachar Lovett
The analytic rank of a tensor, first defined by Gowers and Wolf in the context of higher-order Fourier analysis, is defined to be the logarithm of the bias of the tensor. We prove…
Generalized comparison trees for point-location problems
Daniel M Kane, Shachar Lovett, Shay Moran
Let be an arbitrary family of hyper-planes in -dimensions. We show that the point-location problem for can be solved by a linear decision tree that only uses a special t…
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…
MDS matrices over small fields: A proof of the GM-MDS conjecture
Shachar Lovett
An MDS matrix is a matrix whose minors all have full rank. A question arising in coding theory is what zero patterns can MDS matrices have. There is a natural combinatorial charact…