Search ACM DL

Search Issue

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

DOI: 10.1145/2382559.2382560

The sum of square roots over integers problem is the task of deciding the sign of a nonzero sum, *S* = ∑_{i=1}^{n} *δ*_{i} · √*a*_{i}, where *δ*_{i} ∈...

**A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs**

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

Article No.: 10

DOI: 10.1145/2382559.2382561

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

DOI: 10.1145/2382559.2382562

*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

DOI: 10.1145/2382559.2382563

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