enter search term and/or author name
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
Yuval Filmus, Toniann Pitassi, Rahul Santhanam
Article No.: 5
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 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
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
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. . 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
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 − ε,...