History

Please fill in your query. A complete syntax description you will find on the General Help page.

Result 21 to 40 of 180 total

A status report on the P versus NP question (English)
Advances in Computers 77, 117-147 (2009).
21
Minimizing disjunctive normal form formulas and $\text{AC}^0$ circuits given a truth table. (English)
SIAM J. Comput. 38, No. 1, 63-84 (2008).
22
Amplifying lower bounds by means of self-reducibility. (English)
Electron. Colloq. Comput. Complex. 15, No. 038 (2008).
23
Cracks in the defenses: Scouting out approaches on circuit lower bounds. (English)
Hirsch, Edward A. (ed.) et al., Computer science ‒ theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7‒12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 3-10 (2008).
24
Computational complexity theory (English)
Wiley Encyclopedia of Computer Science and Engineering (2008).
25
Cracks in the defenses: scouting out approaches on circuit lower bounds (English)
CSR, 3-10 (2008).
26
Chipping away at P vs NP: how far are we from proving circuit size lower bounds? (English)
CATS, 3 (2008).
27
Circuit complexity, Kolmogorov complexity, and prospects for lower bounds (English)
DCFS, 7-13 (2008).
28
Amplifying lower bounds by means of self-reducibility (English)
IEEE Conference on Computational Complexity, 31-40 (2008).
29
Reachability problems: an update. (English)
Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18‒23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 25-27 (2007).
30
Reachability problems: an update (English)
CiE, 25-27 (2007).
31
Power from random strings. (English)
SIAM J. Comput. 35, No. 6, 1467-1493 (2006).
32
NL-printable sets and nondeterministic Kolmogorov complexity. (English)
Theor. Comput. Sci. 355, No. 2, 127-138 (2006).
33
What can be efficiently reduced to the Kolmogorov-random strings? (English)
Ann. Pure Appl. Logic 138, No. 1-3, 2-19 (2006).
34
On the complexity of numerical analysis (English)
Complexity of Boolean Functions (2006).
35
Minimizing DNF formulas and $AC^{0}_{d}$ circuits given a truth table (English)
IEEE Conference on Computational Complexity, 237-251 (2006).
36
On the complexity of numerical analysis (English)
IEEE Conference on Computational Complexity, 331-339 (2006).
37
Grid graph reachability problems (English)
IEEE Conference on Computational Complexity, 299-313 (2006).
38
Grid graph reachability problems. (English)
Electron. Colloq. Comput. Complex. 2005, Article No. 149 (2005).
39
The directed planar reachability problem. (English)
Electron. Colloq. Comput. Complex. 2005, Article No. 148 (2005).
40

Result 21 to 40 of 180 total