3 papers
cs.CC2023
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…
math.CO2023
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…
cs.DS2023
A tight lower bound on non-adaptive group testing estimation
Nader H. Bshouty, Tsun-Ming Cheung, Gergely Harcos +2
Efficiently counting or detecting defective items is a crucial task in various fields ranging from biological testing to quality control to streaming algorithms. The \emph{group te…