Zobrazeno 1 - 10
of 2 601
pro vyhledávání: '"A Minzer"'
In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$, and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a finite
Externí odkaz:
http://arxiv.org/abs/2408.09352
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 with soundness $1-\Omega(1)$. As an immediate corollary, we get that un
Externí odkaz:
http://arxiv.org/abs/2407.12762
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], who showed a similar result for almost satisfiable Max-CSPs. Our framew
Externí odkaz:
http://arxiv.org/abs/2408.15377
Autor:
Minzer, Dor, Zheng, Kai Zhe
We show that for all $\varepsilon>0$, for sufficiently large prime power $q$, for all $\delta>0$, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{(1-
Externí odkaz:
http://arxiv.org/abs/2404.07441
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\o
Externí odkaz:
http://arxiv.org/abs/2402.05217
Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $
Externí odkaz:
http://arxiv.org/abs/2402.00850
If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible r
Externí odkaz:
http://arxiv.org/abs/2401.15456
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 games with value less than 1.
Comment: 17 pages
Comment: 17 pages
Externí odkaz:
http://arxiv.org/abs/2312.04783
Autor:
Minzer, Dor, Zheng, Kai Zhe
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 formulated by Kalemaj, Raskhodnikova andVarma, who showed that the propert
Externí odkaz:
http://arxiv.org/abs/2308.15441
Autor:
Bafna, Mitali, Minzer, Dor
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\ll d$) necessarily come from a function over its vertices. More precisely, a direct product test
Externí odkaz:
http://arxiv.org/abs/2308.09668