Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 7 Issue 2, May 2015

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
Yuval Filmus, Toniann Pitassi, Rahul Santhanam
Article No.: 5
DOI: 10.1145/2656209

We give a general transformation that turns polynomial-size Frege proofs into subexponential-size AC0-Frege proofs. This indicates that proving truly exponential lower bounds for AC0-Frege is hard, as it is a long-standing...

Smoothed Complexity Theory
Markus Bläser, Bodo Manthey
Article No.: 6
DOI: 10.1145/2656210

Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng. Classical methods like worst-case or average-case analysis have accompanying complexity classes, such as P and Avg-P, respectively. Whereas worst-case or...

The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
Hubie Chen, Moritz Müller
Article No.: 7
DOI: 10.1145/2751316

We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of Boolean conjunctive queries according to the complexity of this problem. Previous work...

Pebbling, Entropy, and Branching Program Size Lower Bounds
Balagopal Komarath, Jayalal Sarma
Article No.: 8
DOI: 10.1145/2751320

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al. [2012]. Proving a superpolynomial lower bound for the size of nondeterministic thrifty branching...

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups
Ryan O’Donnell, Yi Wu, Yuan Zhou
Article No.: 9
DOI: 10.1145/2751322

In 1997, Håstad showed NP-hardness of (1 − ε, 1/q + δ)-approximating Max-3Lin(Zq); however, it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 − ε,...