Zobrazeno 1 - 10
of 43
pro vyhledávání: '"Mittal, Kunal"'
We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of
Externí odkaz:
http://arxiv.org/abs/2311.07284
We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition
Externí odkaz:
http://arxiv.org/abs/2204.00858
We prove that for every 3-player game with binary questions and answers and value $<1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant $c>0$, such that th
Externí odkaz:
http://arxiv.org/abs/2202.06826
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first e
Externí odkaz:
http://arxiv.org/abs/2107.06156
Autor:
Mittal, Kunal, Raz, Ran
We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connec
Externí odkaz:
http://arxiv.org/abs/2011.09093