Tal Elbaz

dblp:279/6209 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
2since 2021 · last 2026
0009-0005-9627-7251ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Lower Bounds against the Ideal Proof System in Finite Fields
abstract
Lower bounds against strong algebraic proof systems, and specifically fragments of the Ideal Proof System (IPS), have been obtained in an ongoing line of work. With the exception of the placeholder model, where the instance itself lacks small circuits, all existing bounds are proved only over large (or characteristic 0) fields, whereas finite fields form the more natural setting for propositional proof complexity. This work establishes lower bounds against fragments of IPS over constant-sized finite fields, resolving an open problem left by a series of prior works beginning with Forbes, Shpilka, Tzameret, and Wigderson (Theor. of Comput.’21), persisting with Behera, Limaye, Ramanathan, and Srinivasan (ICALP’25), and most recently posed by Forbes (CCC’24). We further highlight the importance of the constant-sized finite field regime in IPS by showing that any hard instance in this regime for a sufficiently strong proof system translates into a hard instance against AC0[p]-Frege, whose lower bounds remain a longstanding open problem.
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu 0007, Iddo Tzameret
STOC1
2021 Approximation Algorithms for Hitting Subgraphs
Noah Brüstle, Tal Elbaz, Hamed Hatami, Onur Kocer, Bingchan Ma
IWOCA2