Zobrazeno 1 - 10
of 182
pro vyhledávání: '"KHOT, SUBHASH A."'
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
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 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
For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ t
Externí odkaz:
http://arxiv.org/abs/2308.06600
We prove a stability result for general $3$-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $\Sigma,\Gamma$ and $\Phi$ are alphabets of constant size, and $\mu$ is a pairwise connected di
Externí odkaz:
http://arxiv.org/abs/2307.16248
We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive
Externí odkaz:
http://arxiv.org/abs/2211.13741
We show improved monotonicity testers for the Boolean hypercube under the $p$-biased measure, as well as over the hypergrid $[m]^n$. Our results are: 1. For any $p\in (0,1)$, for the $p$-biased hypercube we show a non-adaptive tester that makes $\til
Externí odkaz:
http://arxiv.org/abs/2211.09229
Autor:
S., Karthik C., Khot, Subhash
The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique problem where an integer k and a graph G on n vertices are given as input, and the goal i
Externí odkaz:
http://arxiv.org/abs/2112.03983
Given an alphabet size $m\in\mathbb{N}$ thought of as a constant, and $\vec{k} = (k_1,\ldots,k_m)$ whose entries sum of up $n$, the $\vec{k}$-multi-slice is the set of vectors $x\in [m]^n$ in which each symbol $i\in [m]$ appears precisely $k_i$ times
Externí odkaz:
http://arxiv.org/abs/2110.10725
Autor:
Bhangale, Amey, Khot, Subhash
A seminal result of H\r{a}stad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an
Externí odkaz:
http://arxiv.org/abs/2009.02815