4 citations · 5 across the 2 of their papers we have counts for
3 papers
cs.DS2011★ 4 cited
How to Play Unique Games against a Semi-Random Adversary
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several ste…
cs.CC2011
Spectral Algorithms for Unique Games
Alexandra Kolla
We give a new algorithm for Unique Games which is based on purely {\em spectral} techniques, in contrast to previous work in the area, which relies heavily on semidefinite programm…
quant-ph2006★ 1 cited
On parallel composition of zero-knowledge proofs with black-box quantum simulators
Rahul Jain, Alexandra Kolla, Gatis Midrijanis +1
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove…