EDBT 2026 Demo / reviewers in the wild / expert
Tamar Ziegler
dblp:392/2898
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2024
—ORCID · unresolved
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Computational complexity · 100% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
gowers norm |
0.8 | 1 | 2024 | A Dense Model Theorem for the Boolean Slice · FOCS 2024 |
Computational complexity › property testing › algebraic property testing
linearity testing |
0.8 | 1 | 2024 | A Dense Model Theorem for the Boolean Slice · FOCS 2024 |
Computational complexity
property testing |
0.8 | 1 | 2024 | A Dense Model Theorem for the Boolean Slice · FOCS 2024 |
Computational complexity › pseudorandomness
dense model theorem |
0.2 | 1 | 2024 | A Dense Model Theorem for the Boolean Slice · FOCS 2024 |
Methods — techniques the papers use, named apart from their topics
low-degree test · 0.8dense model theorem · 0.8
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | A Dense Model Theorem for the Boolean SliceabstractThe (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let$\varepsilon > 0$and$f$be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple$(x,y,\ z,x\oplus y\oplus z)$of vectors of$2n$bits with exactly$n$ones, the probability that$f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$is at least$1/2+\epsilon$. The linearity testing problem, posed by [6], asks whether there must be an actual linear function that agrees with$f$on$1/2+\epsilon^{\prime}$fraction of the inputs, where$\varepsilon^{\prime}=\in^{\prime}(\in) > 0$. We solve this problem, showing that$f$must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the Boolean hypercube for Gowers uniformity norms. Specifically, we show that for every$k\in \mathbb{N}$, the normalized indicator function of the middle slice of the Boolean hypercube$\{0,1\}^{2n}$is close in Gowers norm to the normalized indicator function of the union of all slices with weight$t=n(\text{mod}\ 2^{k-1})$. Using our techniques we also give a more general ‘low degree test’ and a biased rank theorem for the slice. Gil Kalai, Noam Lifshitz, Dor Minzer, Tamar Ziegler |
FOCS | 4 |