Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Tamar Ziegler

dblp:392/2898 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Computational complexity
gowers norm
0.812024
A Dense Model Theorem for the Boolean Slice · FOCS 2024
Computational complexity › property testing › algebraic property testing
linearity testing
0.812024
A Dense Model Theorem for the Boolean Slice · FOCS 2024
Computational complexity
property testing
0.812024
A Dense Model Theorem for the Boolean Slice · FOCS 2024
Computational complexity › pseudorandomness
dense model theorem
0.212024
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
YearPublicationVenuePosition
2024 A Dense Model Theorem for the Boolean Slice
abstract
The (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
FOCS4