Result 1 to 20 of 82 total
Collapsing and separating completeness notions under average-case and worst-case hypotheses. (English)
Theory Comput. Syst. 51, No. 2, 248-265 (2012).
1
Dimension, halfspaces, and the density of hard sets. (English)
Theory Comput. Syst. 49, No. 3, 601-614 (2011).
2
Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds. (English)
Comput. Complexity 20, No. 2, 329-366 (2011).
3
Unions of disjoint NP-complete sets. (English)
Fu, Bin (ed.) et al., Computing and combinatorics. 17th annual international conference, COCOON 2011, Dallas, TX, USA, August 14‒16, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22684-7/pbk). Lecture Notes in Computer Science 6842, 240-251 (2011).
4
Exact learning algorithms, betting games, and circuit lower bounds. (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, 416-423 (2011).
5
Extracting Kolmogorov complexity with applications to dimension zero-one laws. (English)
Inf. Comput. 209, No. 4, 627-636 (2011).
6
Kolmogorov complexity in randomness extraction (English)
TOCT 3, No. 1, 1 (2011).
7
Exact learning algorithms, betting games, and circuit lower bounds (English)
ICALP (1), 416-423 (2011).
8
Unions of disjoint NP-complete sets (English)
COCOON, 240-251 (2011).
9
Circumventing a ring oscillator approach to FPGA-based hardware trojan detection (English)
ICCD, 289-292 (2011).
10
Collapsing and separating completeness notions under average-case and worst-case hypotheses. (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, 429-440, electronic only (2010).
11
Lower bounds for reducibility to the Kolmogorov random strings. (English)
Ferreira, Fernando (ed.) et al., Programs, proofs, processes. 6th conference on computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June 30‒July 4, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13961-1/pbk). Lecture Notes in Computer Science 6158, 195-200 (2010).
12
Collapsing and separating completeness notions under average-case and worst-case hypotheses. (English)
Comput. Res. Repos. 2010, Article No. 1001.0117 (2010).
13
Collapsing and separating completeness notions under average-case and worst-case hypotheses (English)
STACS, 429-440 (2010).
14
Lower bounds for reducibility to the Kolmogorov random strings (English)
CiE, 195-200 (2010).
15
Kolmogorov complexity in randomness extraction. (English)
Kannan, Ravi (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2009), December 15‒17, 2009, Kanpur, India. Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik (ISBN 978-3-939897-13-2). LIPICS ‒ Leibniz International Proceedings in Informatics 4, 215-226, electronic only (2009).
16
Kolmogorov complexity in randomness extraction (English)
FSTTCS, 215-226 (2009).
17
Scaled dimension and the Kolmogorov complexity of Turing-hard sets. (English)
Theory Comput. Syst. 43, No. 3-4, 471-497 (2008).
18
NP-hard sets are exponentially dense unless NP is contained in conp/poly. (English)
Electron. Colloq. Comput. Complex. 15, No. 022 (2008).
19
Hardness hypotheses, derandomization, and circuit complexity. (English)
Comput. Complexity 17, No. 1, 119-146 (2008).
20
Result 1 to 20 of 82 total
Start
Contact
Print
General Help
