5 papers
Growth of Approximate Groups in Hyperbolic Groups
Michael Saks, Gal Yehuda
We prove a growth dichotomy for infinite approximate groups, and more generally approximate semigroups, in hyperbolic groups. If \(G\) is a finitely generated hyperbolic group and…
Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +3
Gurumuhkani et al. (CCC'24) introduced the local enumeration problem as follows: for a natural number and a parameter , given an -variate -CNF with no sat…
Local Enumeration: The Not-All-Equal Case
Mohit Gurumukhani, Ramamohan Paturi, Michael Saks +1
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number …
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, Martín Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…
Local Enumeration and Majority Lower Bounds
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2
Depth-3 circuit lower bounds and -SAT algorithms are intimately related; the state-of-the-art -circuit lower bound and the -SAT algorithm are based on the same combina…