enter search term and/or author name
On the Sum of Square Roots of Polynomials and Related Problems
Neeraj Kayal, Chandan Saha
Article No.: 9
The sum of square roots over integers problem is the task of deciding the sign of a nonzero sum, S = ∑i=1n δi · √ai, where δi ∈...
A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs
Rafael Pass, Muthuramakrishnan Venkitasubramaniam
Article No.: 10
We show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in...
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
Article No.: 11
The Total Influence (Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I[f]. We...
On the Computational Complexity of Stochastic Controller Optimization in POMDPs
Nikos Vlassis, Michael L. Littman, David Barber
Article No.: 12
We show that the problem of finding an optimal stochastic blind controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard in PSPACE and