Dor Minzer

activity

20192026

most citedGlobal hypercontractivity and its applications

20 citations · 58 across the 39 of their papers we have counts for

collaborators

Showing 2023Show all

10 papers · 1 filter

cs.CC2023

Parallel Repetition of k-Player Projection Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection…

cs.DS2023

Adversarial Low Degree Testing

Dor Minzer, Kai Zhe Zheng

In the $t$ -online-erasure model in property testing, an adversary is allowed to erase $t$ values of a queried function for each query the tester makes. This model was recently form…

cs.CC2023★ 1 cited

Characterizing Direct Product Testing via Coboundary Expansion

Mitali Bafna, Dor Minzer

A $d$ -dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$ -faces (where $k ≪ d$ ) necessarily come fr…

math.CO2023★ 2 cited

Effective Bounds for Restricted $3$ -Arithmetic Progressions in $F_{p}^{n}$

Amey Bhangale, Subhash Khot, Dor Minzer

For a prime $p$ , a restricted arithmetic progression in $F_{p}^{n}$ is a triplet of vectors $x, x + a, x + 2 a$ in which the common difference $a$ is a non-zero element from $\{0,1…

math.PR2023

Influences in Mixing Measures

Frederic Koehler, Noam Lifshitz, Dor Minzer +1

The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately conn…

cs.CC2023★ 1 cited

On Approximability of Satisfiable k-CSPs: IV

Amey Bhangale, Subhash Khot, Dor Minzer

We prove a stability result for general $3$ -wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $Σ, Γ$ and $Φ$ are alphabe…

math.PR2023

On Perfectly Friendly Bisections of Random Graphs

Dor Minzer, Ashwin Sah, Mehtaab Sawhney

We prove that there exists a constant $γ_{crit} \approx .17566$ such that if $G \sim G (n, 1/2)$ then for any $ε > 0$ with high probability $G$ has a equipa…

cs.CC2023

Solving Unique Games over Globally Hypercontractive Graphs

Mitali Bafna, Dor Minzer

We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct charact…

cs.CC2023

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

Dor Minzer, Kai Zheng

A local tester for an error correcting code $C \subseteq Σ^{n}$ is a tester that makes $Q$ oracle queries to a given word $w \in Σ^{n}$ and decides to accept or reject the word $w$ . An…

math.CO2023

On $t$ -Intersecting Families of Permutations

Nathan Keller, Noam Lifshitz, Dor Minzer +1

We prove that there exists a constant $c_{0}$ such that for any $t \in N$ and any $n \geq c_{0} t$ , if $A \subset S_{n}$ is a $t$ -intersecting family of permutations then$|A|\leq…

Parallel Repetition of k-Player Projection Games

Adversarial Low Degree Testing

Characterizing Direct Product Testing via Coboundary Expansion

Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn​

Influences in Mixing Measures

On Approximability of Satisfiable k-CSPs: IV

On Perfectly Friendly Bisections of Random Graphs

Solving Unique Games over Globally Hypercontractive Graphs

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

On t-Intersecting Families of Permutations

Effective Bounds for Restricted $3$ -Arithmetic Progressions in $F_{p}^{n}$

On $t$ -Intersecting Families of Permutations