3 citations · 6 across the 6 of their papers we have counts for
9 papers
Superpolynomial lower bounds for vertex numbers of real projective space triangulations via a topological Figiel-Lindenstrauss-Milman theorem
Florian Frick, Kaave Hosseini, Eric Myzelev +2
We prove that every simplicial triangulation of real projective -space has vertices. Together with known constructions, this determines the minimum vertex num…
A -Topological Framework for Sign-rank Lower Bounds
Florian Frick, Kaave Hosseini, Aliaksei Vasileuski
We develop a topological framework for proving lower bounds on sign-rank via -equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance pr…
Refuting approaches to the log-rank conjecture for XOR functions
Hamed Hatami, Kaave Hosseini, Shachar Lovett +1
The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on poten…
Sparse graph counting and Kelley-Meka bounds for binary systems
Yuval Filmus, Hamed Hatami, Kaave Hosseini +1
In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In thi…
Online Learning and Disambiguations of Partial Concept Classes
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami +1
In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central quest…
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…