Ausgabe 2/2013
Selected papers from the 27th Annual IEEE Conference on Computational Complexity (CCC 2012)
Inhalt (8 Artikel)
Special Issue “Conference on Computational Complexity 2012” Guest editors’ foreword
Boaz Barak, Irit Dinur
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
Kazuhisa Seto, Suguru Tamaki
DNF sparsification and a faster deterministic counting algorithm
Parikshit Gopalan, Raghu Meka, Omer Reingold
Amplifying circuit lower bounds against polynomial time, with applications
Richard J. Lipton, Ryan Williams
Is Valiant–Vazirani’s isolation probability improvable?
Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe