Result 1 to 20 of 249 total
Inseparability and strong hypotheses for disjoint NP pairs. (English)
Theory Comput. Syst. 51, No. 2, 229-247 (2012).
1
Low-depth witnesses are easy to find. (English)
Comput. Complexity 21, No. 3, 479-497 (2012).
2
Robust simulations and significant separations. (English)
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4‒8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 569-580 (2011).
3
Repeated matching pennies with limited randomness. (English)
Comput. Res. Repos. 2011, Article No. 1102.1096 (2011).
4
Complexity classes of equivalence problems revisited. (English)
Inf. Comput. 209, No. 4, 748-763 (2011).
5
Extracting Kolmogorov complexity with applications to dimension zero-one laws. (English)
Inf. Comput. 209, No. 4, 627-636 (2011).
6
Infeasibility of instance compression and succinct PCPs for NP. (English)
J. Comput. Syst. Sci. 77, No. 1, 91-106 (2011).
7
Robust simulations and significant separations (English)
ICALP (1), 569-580 (2011).
8
Repeated matching pennies with limited randomness (English)
ACM Conference on Electronic Commerce, 111-118 (2011).
9
Proceedings of the 43rd ACM symposium on theory of computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 (English)
STOC (2011).
10
Inseparability and strong hypotheses for disjoint NP pairs. (English)
Marion, Jean-Yves (ed.) et al., STACS 2010. 27th international symposium on theoretical aspects of computer science, Nancy, France, March 4‒6, 2010. Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik (ISBN 978-3-939897-16-3). LIPICS ‒ Leibniz International Proceedings in Informatics 5, 395-404, electronic only (2010).
11
Does the polynomial hierarchy collapse if onto functions are invertible? (English)
Theory Comput. Syst. 46, No. 1, 143-156 (2010).
12
Inseparability and strong hypotheses for disjoint NP pairs (English)
STACS, 395-404 (2010).
13
Bounding rationality by discounting time (English)
ICS, 143-155 (2010).
14
Derandomizing from random strings (English)
IEEE Conference on Computational Complexity, 58-63 (2010).
15
A simple proof of Toda’s theorem. (English)
Theory Comput. 5, Paper No. 7, 135-140, electronic only (2009).
16
Derandomizing from random strings. (English)
Comput. Res. Repos. 2009, Article No. 0912.3162 (2009).
17
Bounding rationality by discounting time. (English)
Comput. Res. Repos. 2009, Article No. 0911.3162 (2009).
18
Complexity classes of equivalence problems revisited. (English)
Comput. Res. Repos. 2009, Article No. 0907.4775 (2009).
19
The status of the P versus NP problem. (English)
Commun. ACM 52, No. 9, 78-86 (2009).
20
Result 1 to 20 of 249 total
Start
Contact
Print
General Help
