Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 4 Issue 4, November 2012

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=1n δi · √ai, 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 sqrt-sum-hard, hence placing it in NP would imply...