VLDB 2026 Research / reviewers in the wild / expert
Tal Elbaz
dblp:279/6209
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Lower Bounds against the Ideal Proof System in Finite FieldsabstractLower 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 |
STOC | 1 |
| 2021 | Approximation Algorithms for Hitting Subgraphs
Noah Brüstle, Tal Elbaz, Hamed Hatami, Onur Kocer, Bingchan Ma |
IWOCA | 2 |