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 2024Show all

11 papers · 1 filter

cs.DC2024

Constant Degree Networks for Almost-Everywhere Reliable Transmission

Mitali Bafna, Dor Minzer

In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network $G$ that sup…

math.CO2024★ 1 cited

Reasonable Bounds for Combinatorial Lines of Length Three

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove that any subset $A \subseteq [3]^{n}$ with $3^{- n} ∣ A ∣ \geq (lo g lo g lo g lo g n)^{- c}$ contains a combinatorial line of length $3$ , i.e., $x, y, z \in A$ , not all equal, with…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VII

Amey Bhangale, Subhash Khot, Yang P. Liu +1

Let $Σ_{1}, \dots, Σ_{k}$ be finite alphabets, and let $μ$ be a distribution over $Σ_{1} \times \dots \times Σ_{k}$ in which the probability of each atom is at least $α$ . We prove that if $…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VI

Amey Bhangale, Subhash Khot, Yang P. Liu +1

We prove local and global inverse theorems for general $3$ -wise correlations over pairwise-connected distributions. Let $μ$ be a distribution over $Σ \times Γ \times Φ$ such that the…

cs.CC2024

Parallel Repetition for $3$ -Player XOR Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

In a $3$ - $XOR$ game $G$ , the verifier samples a challenge $(x, y, z) \sim μ$ where $μ$ is a probability distribution over $Σ \times Γ \times Φ$ , and a map $t\colon Σ\ti…

cs.CC2024★ 2 cited

On Approximability of Satisfiable k-CSPs: V

Amey Bhangale, Subhash Khot, Dor Minzer

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], w…

cs.CC2024★ 2 cited

Quasi-Linear Size PCPs with Small Soundness from HDX

Mitali Bafna, Dor Minzer, Nikhil Vyas

We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs w…

cs.CC2024

Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer, Kai Zhe Zheng

We show that for all $ε > 0$ , for sufficiently large $q \in N$ power of $2$ , for all $δ > 0$ , it is NP-hard to distinguish whether a given $2$ -Prover- $1$ -Round project…

math.CO2024

A Dense Model Theorem for the Boolean Slice

Gil Kalai, Noam Lifshitz, Dor Minzer +1

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $ε > 0$ and $f$ be a function on the middle slice on the Boolean c…

cs.CC2024★ 2 cited

Constant Degree Direct Product Testers with Small Soundness

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$ -dimensional simplicial complex. A function $F : X (k) \to {0, 1}^{k}$ is said to be a direct product function if there exists a function $f : X (1) \to {0, 1}$ …

math.CO2024

Product Mixing in Compact Lie Groups

David Ellis, Guy Kindler, Noam Lifshitz +1

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $x y = z$ has no solutions with $x, y, z \in S$ . For $D \in N$ , a group $G$ is said to be $D$ -quas…

Constant Degree Networks for Almost-Everywhere Reliable Transmission

Reasonable Bounds for Combinatorial Lines of Length Three

On Approximability of Satisfiable k-CSPs: VII

On Approximability of Satisfiable k-CSPs: VI

Parallel Repetition for 3-Player XOR Games

On Approximability of Satisfiable k-CSPs: V

Quasi-Linear Size PCPs with Small Soundness from HDX

Near Optimal Alphabet-Soundness Tradeoff PCPs

A Dense Model Theorem for the Boolean Slice

Constant Degree Direct Product Testers with Small Soundness

Product Mixing in Compact Lie Groups

On Approximability of Satisfiable $k$ -CSPs: VII

On Approximability of Satisfiable $k$ -CSPs: VI

Parallel Repetition for $3$ -Player XOR Games