Danner, Norman; Royer, James S. Adventures in time and space. (English) Zbl 1370.03059 Proceedings of the 33rd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’06, Charleston, SC, USA, January 11–13, 2006. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-59593-027-2). 168-179 (2006). MSC: 03D15 03B70 03D65 68N30 68Q15 68Q55 PDFBibTeX XMLCite \textit{N. Danner} and \textit{J. S. Royer}, in: Proceedings of the 33rd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL '06, Charleston, SC, USA, January 11--13, 2006. New York, NY: Association for Computing Machinery (ACM). 168--179 (2006; Zbl 1370.03059) Full Text: DOI
Roşu, Grigore Equality of streams is a \({\Pi}^0_2\)-complete problem. (English) Zbl 1321.68288 Proceedings of the 11th ACM SIGPLAN international conference on functional programming, ICFP ’06, Portland, OR, USA, September 18–20, 2006. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-59593-309-3). ACM SIGPLAN Notices 41, No. 9, 184-191 (2006). MSC: 68Q17 68Q15 68Q25 PDFBibTeX XMLCite \textit{G. Roşu}, in: Proceedings of the 11th ACM SIGPLAN international conference on functional programming, ICFP '06, Portland, OR, USA, September 18--20, 2006. New York, NY: Association for Computing Machinery (ACM). 184--191 (2006; Zbl 1321.68288) Full Text: DOI
Akavia, Adi; Goldreich, Oded; Goldwasser, Shafi; Moshkovitz, Dana On basing one-way functions on NP-hardness. (English) Zbl 1302.68132 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 701-710 (2006); erratum in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM). 795–796 (2010). MSC: 68Q25 68Q15 68Q17 68W20 94A60 PDFBibTeX XMLCite \textit{A. Akavia} et al., in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 701--710 (2006; Zbl 1302.68132) Full Text: DOI
Impagliazzo, Russell Can every randomized algorithm be derandomized? (English) Zbl 1301.68136 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 373-374 (2006). MSC: 68Q15 68Q25 68W20 PDFBibTeX XMLCite \textit{R. Impagliazzo}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 373--374 (2006; Zbl 1301.68136) Full Text: DOI
Micali, Silvio; Pass, Rafael Local zero knowledge. (English) Zbl 1301.94123 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 306-315 (2006). MSC: 94A60 68Q15 94A62 PDFBibTeX XMLCite \textit{S. Micali} and \textit{R. Pass}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 306--315 (2006; Zbl 1301.94123) Full Text: DOI
Watrous, John Zero-knowledge against quantum attacks. (English) Zbl 1301.68131 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 296-305 (2006). MSC: 68Q12 68Q15 81P94 94A62 PDFBibTeX XMLCite \textit{J. Watrous}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 296--305 (2006; Zbl 1301.68131) Full Text: DOI arXiv
Nguyen, Minh-Huyen; Vadhan, Salil Zero knowledge with efficient provers. (English) Zbl 1301.94124 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 287-295 (2006). MSC: 94A60 68Q15 68Q25 94A62 PDFBibTeX XMLCite \textit{M.-H. Nguyen} and \textit{S. Vadhan}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 287--295 (2006; Zbl 1301.94124) Full Text: DOI
Dinur, Irit The PCP theorem by gap amplification. (English) Zbl 1301.68133 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 241-250 (2006). MSC: 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{I. Dinur}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 241--250 (2006; Zbl 1301.68133) Full Text: DOI
Samorodnitsky, Alex; Trevisan, Luca Gowers uniformity, influence of variables, and PCPs. (English) Zbl 1301.68137 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 11-20 (2006). MSC: 68Q15 05C65 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{A. Samorodnitsky} and \textit{L. Trevisan}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 11--20 (2006; Zbl 1301.68137) Full Text: DOI
Gajnutdinova, A. F. On simulating quantum and classical branching programs. (Russian) Zbl 1249.68078 Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 1, 45-64 (2006). MSC: 68Q15 68Q12 68Q45 PDFBibTeX XMLCite \textit{A. F. Gajnutdinova}, Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 1, 45--64 (2006; Zbl 1249.68078)
Nielsen, Michael A.; Dowling, Mark R.; Gu, Mile; Doherty, Andrew C. Quantum computation as geometry. (English) Zbl 1226.81049 Science 311, No. 5764, 1133-1135 (2006). MSC: 81P68 49S05 58E10 68Q05 68Q15 94A15 PDFBibTeX XMLCite \textit{M. A. Nielsen} et al., Science 311, No. 5764, 1133--1135 (2006; Zbl 1226.81049) Full Text: DOI arXiv
Raz, Ran Separation of multilinear circuit and formula size. (English) Zbl 1213.68301 Theory Comput. 2, Paper No. 6, 121-135 (2006). MSC: 68Q15 68Q17 68Q25 94C05 PDFBibTeX XMLCite \textit{R. Raz}, Theory Comput. 2, Paper No. 6, 121--135 (2006; Zbl 1213.68301) Full Text: DOI
Sipos, Ádḿ; Pataki, Norbert; Porkoláb, Zoltán On multiparadigm software complexity metrics. (English) Zbl 1224.68023 PU.M.A., Pure Math. Appl. 17, No. 3-4, 469-482 (2006). MSC: 68N30 68Q15 68N19 PDFBibTeX XMLCite \textit{Á. Sipos} et al., PU.M.A., Pure Math. Appl. 17, No. 3--4, 469--482 (2006; Zbl 1224.68023)
Cook, Stephen The P versus NP problem. (English) Zbl 1194.68001 Carlson, J. (ed.) et al., The millennium prize problems. Providence, RI: American Mathematical Society (AMS); Cambridge, MA: Clay Mathematics Institute (ISBN 0-8218-3679-X/hbk). 87-104 (2006). MSC: 68-01 68Q15 PDFBibTeX XMLCite \textit{S. Cook}, in: The Millennium Prize problems. Providence, RI: American Mathematical Society (AMS); Cambridge, MA: Clay Mathematics Institute. 87--104 (2006; Zbl 1194.68001)
Baier, Christel; Bertrand, Nathalie; Schnoebelen, Philippe A note on the attractor-property of infinite-state Markov chains. (English) Zbl 1191.68330 Inf. Process. Lett. 97, No. 2, 58-63 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{C. Baier} et al., Inf. Process. Lett. 97, No. 2, 58--63 (2006; Zbl 1191.68330) Full Text: DOI
Caporaso, Salvatore A decidable characterization of the classes between lintime and exptime. (English) Zbl 1185.68348 Inf. Process. Lett. 97, No. 1, 36-40 (2006). MSC: 68Q17 68Q15 68Q05 PDFBibTeX XMLCite \textit{S. Caporaso}, Inf. Process. Lett. 97, No. 1, 36--40 (2006; Zbl 1185.68348) Full Text: DOI
Feige, Uriel; Reichman, Daniel On the hardness of approximating max-satisfy. (English) Zbl 1185.68350 Inf. Process. Lett. 97, No. 1, 31-35 (2006). MSC: 68Q17 68Q15 68W25 PDFBibTeX XMLCite \textit{U. Feige} and \textit{D. Reichman}, Inf. Process. Lett. 97, No. 1, 31--35 (2006; Zbl 1185.68350) Full Text: DOI
Su, Li Sek Subproblems and NP-completeness theory. (English) Zbl 1169.68433 Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 90, 192-198 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{L. S. Su}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 90, 192--198 (2006; Zbl 1169.68433)
Tesson, Pascal; Thérien, Denis Bridges between algebraic automata theory and complexity theory. (English) Zbl 1169.68434 Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 88, 37-64 (2006). MSC: 68Q15 68Q70 PDFBibTeX XMLCite \textit{P. Tesson} and \textit{D. Thérien}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 88, 37--64 (2006; Zbl 1169.68434)
Sipser, Michael Introduction to the theory of computation. 2nd. ed. (English) Zbl 1191.68311 Boston, MA: Thompson (ISBN 978-0-619-21764-8). xvii, 437 p. (2006). MSC: 68Q05 68-01 68Q15 68W05 PDFBibTeX XMLCite \textit{M. Sipser}, Introduction to the theory of computation. 2nd. ed. Boston, MA: Thompson (2006; Zbl 1191.68311)
Mubarakzyanov, R. G. Lower bounds of complexity of probabilistic branching programs with a big ordered part. (English. Russian original) Zbl 1175.68184 Russ. Math. 50, No. 6, 54-62 (2006); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2006, No. 6, 56-64 (2006). MSC: 68Q15 68Q17 60C05 PDFBibTeX XMLCite \textit{R. G. Mubarakzyanov}, Russ. Math. 50, No. 6, 54--62 (2006; Zbl 1175.68184); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2006, No. 6, 56--64 (2006)
Bonfante, Guillaume Some programming languages for Logspace and Ptime. (English) Zbl 1236.68074 Johnson, Michael (ed.) et al., Algebraic methodology and software technology. 11th international conference, AMAST 2006, Kuressaare, Estonia, July 5–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35633-2/pbk). Lecture Notes in Computer Science 4019, 66-80 (2006). MSC: 68Q15 68N15 PDFBibTeX XMLCite \textit{G. Bonfante}, Lect. Notes Comput. Sci. 4019, 66--80 (2006; Zbl 1236.68074) Full Text: DOI Link
Glaßer, Christian; Travers, Stephen; Wagner, Klaus W. Perfect correspondences between dot-depth and polynomial-time hierarchy. (English) Zbl 1227.68028 Ibarra, Oscar H. (ed.) et al., Developments in language theory. 10th international conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006. Proceedings. Berlin: Springer (ISBN 3-540-35428-X/pbk). Lecture Notes in Computer Science 4036, 408-419 (2006). MSC: 68Q15 68Q45 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Lect. Notes Comput. Sci. 4036, 408--419 (2006; Zbl 1227.68028) Full Text: DOI
Björklund, Andreas; Husfeldt, Thore Exact algorithms for exact satisfiability and number of perfect matchings. (English) Zbl 1170.68651 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 548-559 (2006). MSC: 68W05 05A15 05C70 68Q15 68Q25 90C27 PDFBibTeX XMLCite \textit{A. Björklund} and \textit{T. Husfeldt}, Lect. Notes Comput. Sci. 4051, 548--559 (2006; Zbl 1170.68651) Full Text: DOI
Hitchcock, John M.; Pavan, A. Comparing reductions to NP-complete sets. (English) Zbl 1223.68046 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 465-476 (2006). MSC: 68Q17 68Q15 PDFBibTeX XMLCite \textit{J. M. Hitchcock} and \textit{A. Pavan}, Lect. Notes Comput. Sci. 4051, 465--476 (2006; Zbl 1223.68046) Full Text: DOI
Hoang, Thanh Minh; Mahajan, Meena; Thierauf, Thomas On the bipartite unique perfect matching problem. (English) Zbl 1223.68057 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 453-464 (2006). MSC: 68Q25 05C70 68Q15 PDFBibTeX XMLCite \textit{T. M. Hoang} et al., Lect. Notes Comput. Sci. 4051, 453--464 (2006; Zbl 1223.68057) Full Text: DOI
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza N.; Papadimitriou, Christos H. The connectivity of Boolean satisfiability: computational and structural dichotomies. (English) Zbl 1201.03023 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 346-357 (2006). MSC: 03D15 03B05 05C40 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. Gopalan} et al., Lect. Notes Comput. Sci. 4051, 346--357 (2006; Zbl 1201.03023) Full Text: DOI
Grohe, Martin; Verbitsky, Oleg Testing graph isomorphism in parallel by playing a game. (English) Zbl 1223.68056 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 3-14 (2006). MSC: 68Q25 03C13 05C85 68Q15 68Q19 68W10 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{O. Verbitsky}, Lect. Notes Comput. Sci. 4051, 3--14 (2006; Zbl 1223.68056) Full Text: DOI arXiv
Schöpp, Ulrich Space-efficient computation by interaction. A type system for logarithmic space. (English) Zbl 1225.68058 Ésik, Zoltán (ed.), Computer science logic. 20th international workshop, CSL 2006, 15th annual conference of the EACSL, Szeged, Hungary, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-45458-8/pbk). Lecture Notes in Computer Science 4207, 606-621 (2006). MSC: 68N18 68Q15 PDFBibTeX XMLCite \textit{U. Schöpp}, Lect. Notes Comput. Sci. 4207, 606--621 (2006; Zbl 1225.68058) Full Text: DOI
Bonfante, G.; Kahle, R.; Marion, J.-Y.; Oitavem, I. Towards an implicit characterization of NC\(^{k}\). (English) Zbl 1225.68091 Ésik, Zoltán (ed.), Computer science logic. 20th international workshop, CSL 2006, 15th annual conference of the EACSL, Szeged, Hungary, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-45458-8/pbk). Lecture Notes in Computer Science 4207, 212-224 (2006). MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{G. Bonfante} et al., Lect. Notes Comput. Sci. 4207, 212--224 (2006; Zbl 1225.68091) Full Text: DOI
Hunt, Harry B. III; Marathe, Madhav V.; Rosenkrantz, Daniel J.; Stearns, Richard E. Towards a predictive computational complexity theory for periodically specified problems: a survey. (English) Zbl 1156.82357 Percus, Allon (ed.) et al., Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press (ISBN 0-19-517738-X/pbk). Santa Fe Institute Studies in the Sciences of Complexity, 285-318 (2006). MSC: 82B44 68T20 68Q15 05C80 PDFBibTeX XMLCite \textit{H. B. Hunt III} et al., in: Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press. 285--318 (2006; Zbl 1156.82357)
Mertens, Stephan The easiest hard problem: number partitioning. (English) Zbl 1156.82321 Percus, Allon (ed.) et al., Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press (ISBN 0-19-517738-X/pbk). Santa Fe Institute Studies in the Sciences of Complexity, 125-139 (2006). MSC: 82-08 68Q15 68Q25 82B26 PDFBibTeX XMLCite \textit{S. Mertens}, in: Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press. 125--139 (2006; Zbl 1156.82321) Full Text: arXiv
Cocco, Simona; Monasson, Rémi; Montanari, Andrea; Semerjian, Guilhem Analyzing search algorithms with physical methods. (English) Zbl 1156.82316 Percus, Allon (ed.) et al., Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press (ISBN 0-19-517738-X/pbk). Santa Fe Institute Studies in the Sciences of Complexity, 63-105 (2006). MSC: 82-08 68Q25 68P10 68Q15 PDFBibTeX XMLCite \textit{S. Cocco} et al., in: Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press. 63--105 (2006; Zbl 1156.82316)
Kalai, Gil; Safra, Shmuel Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. (English) Zbl 1156.82317 Percus, Allon (ed.) et al., Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press (ISBN 0-19-517738-X/pbk). Santa Fe Institute Studies in the Sciences of Complexity, 25-60 (2006). MSC: 82-08 65Y20 68Q15 68Q25 PDFBibTeX XMLCite \textit{G. Kalai} and \textit{S. Safra}, in: Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press. 25--60 (2006; Zbl 1156.82317)
Percus, Allon G.; Istrate, Gabriel; Moore, Cristopher Introduction: where statistical physics meets computation. (English) Zbl 1156.82322 Percus, Allon (ed.) et al., Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press (ISBN 0-19-517738-X/pbk). Santa Fe Institute Studies in the Sciences of Complexity, 3-24 (2006). MSC: 82-08 65Y20 68Q10 68Q15 PDFBibTeX XMLCite \textit{A. G. Percus} et al., in: Computational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algorithmic complexity, Los Angeles, CA, USA, June 2002. Oxford: Oxford University Press. 3--24 (2006; Zbl 1156.82322)
Goldreich, Oded; Sudan, Madhu Locally testable codes and PCPs of almost-linear length. (English) Zbl 1315.94144 J. ACM 53, No. 4, 558-655 (2006). MSC: 94B60 94B05 68Q15 68W20 PDFBibTeX XMLCite \textit{O. Goldreich} and \textit{M. Sudan}, J. ACM 53, No. 4, 558--655 (2006; Zbl 1315.94144) Full Text: DOI
Petrides, George; Mykkeltveit, Johannes On the classification of periodic binary sequences into nonlinear complexity classes. (English) Zbl 1152.94393 Gong, Guang (ed.) et al., Sequences and their applications – SETA 2006. 4th international conference, Beijing, China, September 24–28, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-44523-4/pbk). Lecture Notes in Computer Science 4086, 209-222 (2006). MSC: 94A55 68Q15 PDFBibTeX XMLCite \textit{G. Petrides} and \textit{J. Mykkeltveit}, Lect. Notes Comput. Sci. 4086, 209--222 (2006; Zbl 1152.94393) Full Text: DOI
Michailidis, Panagiotis D.; Typou, Theodoros; Stefanidis, Vasilis; Margaritis, Konstantinos G. Performance models for matrix computations on networks of heterogeneous workstations. (English) Zbl 1160.68318 Neural Parallel Sci. Comput. 14, No. 2-3, 177-204 (2006). MSC: 68M10 65F30 65Y10 65Y20 PDFBibTeX XMLCite \textit{P. D. Michailidis} et al., Neural Parallel Sci. Comput. 14, No. 2--3, 177--204 (2006; Zbl 1160.68318)
Arratia, Argimiro; Ortiz, Carlos E. Counting proportions of sets: Expressive power with almost order. (English) Zbl 1145.68431 Correa, José R. (ed.) et al., LATIN 2006: Theoretical informatics. 7th Latin American symposium, Valdivia, Chile, March 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-32755-X/pbk). Lecture Notes in Computer Science 3887, 105-117 (2006). MSC: 68Q19 03C13 03C80 68Q15 91A46 PDFBibTeX XMLCite \textit{A. Arratia} and \textit{C. E. Ortiz}, Lect. Notes Comput. Sci. 3887, 105--117 (2006; Zbl 1145.68431) Full Text: DOI
Bogdanov, Andrej; Trevisan, Luca Average-case complexity. (English) Zbl 1143.68401 Found. Trends Theor. Comput. Sci. 2, No. 1, 111 p. (2006). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Bogdanov} and \textit{L. Trevisan}, Found. Trends Theor. Comput. Sci. 2, No. 1, 111~p. (2006; Zbl 1143.68401) Full Text: DOI
Pérez Jiménez, Mario J.; Romero Jiménez, Álvaro; Sancho Caparrini, Fernando A polynomial complexity class in P systems using membrane division. (English) Zbl 1145.68426 J. Autom. Lang. Comb. 11, No. 4, 423-434 (2006). MSC: 68Q15 68Q10 PDFBibTeX XMLCite \textit{M. J. Pérez Jiménez} et al., J. Autom. Lang. Comb. 11, No. 4, 423--434 (2006; Zbl 1145.68426)
Hoory, Shlomo; Linial, Nathan; Wigderson, Avi Expander graphs and their applications. (English) Zbl 1147.68608 Bull. Am. Math. Soc., New Ser. 43, No. 4, 439-561 (2006). Reviewer: Olaf Ninnemann (Uffing am Staffelsee) MSC: 68R10 68-02 05-02 68Q15 68Q17 94B05 05C25 05C80 PDFBibTeX XMLCite \textit{S. Hoory} et al., Bull. Am. Math. Soc., New Ser. 43, No. 4, 439--561 (2006; Zbl 1147.68608) Full Text: DOI
Bonfante, Guillaume; Marion, Jean-Yves; Péchoux, Romain A characterization of alternating log time by first order functional programs. (English) Zbl 1138.68357 Hermann, Miki (ed.) et al., Logic for programming, artificial intelligence, and reasoning. 13th international conference, LPAR 2006, Phnom Penh, Cambodia, November 13–17, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-48281-9/pbk). Lecture Notes in Computer Science 4246. Lecture Notes in Artificial Intelligence, 90-104 (2006). MSC: 68N30 68N18 68Q15 PDFBibTeX XMLCite \textit{G. Bonfante} et al., Lect. Notes Comput. Sci. 4246, 90--104 (2006; Zbl 1138.68357) Full Text: DOI Link
Pavan, A.; Santhanam, Rahul; Vinodchandran, N. V. Some results on average-case hardness within the polynomial hierarchy. (English) Zbl 1177.68096 Arun-Kumar, S. (ed.) et al., FSTTCS 2006: Foundations of software technology and theoretical computer science. 26th international conference, Kolkata, India, December 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49994-7/pbk). Lecture Notes in Computer Science 4337, 188-199 (2006). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Pavan} et al., Lect. Notes Comput. Sci. 4337, 188--199 (2006; Zbl 1177.68096) Full Text: DOI Link
Chakraborty, Tanmoy; Datta, Samir One-input-face MPCVP is hard for L, but in LogDCFL. (English) Zbl 1177.68099 Arun-Kumar, S. (ed.) et al., FSTTCS 2006: Foundations of software technology and theoretical computer science. 26th international conference, Kolkata, India, December 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49994-7/pbk). Lecture Notes in Computer Science 4337, 57-68 (2006). MSC: 68Q25 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{T. Chakraborty} and \textit{S. Datta}, Lect. Notes Comput. Sci. 4337, 57--68 (2006; Zbl 1177.68099) Full Text: DOI
Grigorieva, Elena; Herings, P. Jean-Jacques; Müller, Rudolf; Vermeulen, Dries The communication complexity of private value single-item auctions. (English) Zbl 1133.91380 Oper. Res. Lett. 34, No. 5, 491-498 (2006). MSC: 91B26 91A28 68Q15 PDFBibTeX XMLCite \textit{E. Grigorieva} et al., Oper. Res. Lett. 34, No. 5, 491--498 (2006; Zbl 1133.91380) Full Text: DOI Link
Healy, Alexander; Viola, Emanuele Constant-depth circuits for arithmetic in finite fields of characteristic two. (English) Zbl 1137.68027 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 672-683 (2006). MSC: 68Q15 11Y16 11T06 68Q25 94C10 PDFBibTeX XMLCite \textit{A. Healy} and \textit{E. Viola}, Lect. Notes Comput. Sci. 3884, 672--683 (2006; Zbl 1137.68027) Full Text: DOI
Limaye, Nutan; Mahajan, Meena; Sarma M. N., Jayalal Evaluating monotone circuits on cylinders, planes and tori. (English) Zbl 1136.68405 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 660-671 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{N. Limaye} et al., Lect. Notes Comput. Sci. 3884, 660--671 (2006; Zbl 1136.68405) Full Text: DOI
Roy, Amitabha; Straubing, Howard Definability of languages by generalized first-order formulas over \((\mathbb{N},+)\). (English) Zbl 1136.03321 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 489-499 (2006). MSC: 03D05 03C13 03C80 20M35 68Q15 68Q45 PDFBibTeX XMLCite \textit{A. Roy} and \textit{H. Straubing}, Lect. Notes Comput. Sci. 3884, 489--499 (2006; Zbl 1136.03321) Full Text: DOI
Fortnow, Lance; Klivans, Adam R. Linear advice for randomized logarithmic space. (English) Zbl 1136.68404 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 469-476 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{L. Fortnow} and \textit{A. R. Klivans}, Lect. Notes Comput. Sci. 3884, 469--476 (2006; Zbl 1136.68404) Full Text: DOI
Buhrman, Harry; Torenvliet, Leen; Unger, Falk Sparse selfreducible sets and polynomial size circuit lower bounds. (English) Zbl 1136.68403 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 455-468 (2006). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{H. Buhrman} et al., Lect. Notes Comput. Sci. 3884, 455--468 (2006; Zbl 1136.68403) Full Text: DOI
Glaßer, Christian; Pavan, A.; Selman, Alan L.; Zhang, Liyu Redundancy in complete sets. (English) Zbl 1136.68027 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 444-454 (2006). MSC: 68Q15 68Q17 03D30 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Lect. Notes Comput. Sci. 3884, 444--454 (2006; Zbl 1136.68027) Full Text: DOI
Hitchcock, John M. Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. (English) Zbl 1136.68406 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 408-419 (2006). MSC: 68Q17 68Q15 68Q25 68Q32 PDFBibTeX XMLCite \textit{J. M. Hitchcock}, Lect. Notes Comput. Sci. 3884, 408--419 (2006; Zbl 1136.68406) Full Text: DOI arXiv
Chakaravarthy, Venkatesan T.; Roy, Sambuddha Oblivious symmetric alternation. (English) Zbl 1137.68026 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 230-241 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{V. T. Chakaravarthy} and \textit{S. Roy}, Lect. Notes Comput. Sci. 3884, 230--241 (2006; Zbl 1137.68026) Full Text: DOI
Wehner, Stephanie Entanglement in interactive proof systems with binary answers. (English) Zbl 1136.68516 Durand, Bruno (ed.) et al., STACS 2006. 23rd annual symposium on theoretical aspects of computer science, Marseille, France, February 23–25, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-32301-3/pbk). Lecture Notes in Computer Science 3884, 162-171 (2006). MSC: 68T15 68Q15 68Q25 PDFBibTeX XMLCite \textit{S. Wehner}, Lect. Notes Comput. Sci. 3884, 162--171 (2006; Zbl 1136.68516) Full Text: DOI
Wainer, Stanley S. Recursion and proofs. (English) Zbl 1127.03325 Schwichtenberg, Helmut (ed.) et al., Proof technology and computation. Papers from the summer school, Marktoberdorf, Germany, July 29–August 10, 2003. Amsterdam: IOS Press (ISBN 1-58603-625-4/hbk). NATO Science Series III: Computer & Systems Sciences 200, 417-444 (2006). MSC: 03D20 03D15 03F20 68Q15 03-01 03-02 PDFBibTeX XMLCite \textit{S. S. Wainer}, NATO Sci. Ser. III, Comput. Syst. Sci. 200, 417--444 (2006; Zbl 1127.03325)
Jones, Neil D. Selected topics on computability, complexity, and termination. (English) Zbl 1143.68396 Schwichtenberg, Helmut (ed.) et al., Proof technology and computation. Papers from the summer school, Marktoberdorf, Germany, July 29–August 10, 2003. Amsterdam: IOS Press (ISBN 1-58603-625-4/hbk). NATO Science Series III: Computer & Systems Sciences 200, 207-246 (2006). MSC: 68Q05 68N30 68Q15 68Q25 03D20 PDFBibTeX XMLCite \textit{N. D. Jones}, NATO Sci. Ser. III, Comput. Syst. Sci. 200, 207--246 (2006; Zbl 1143.68396)
Gál, Anna (ed.) Special issue: Selected papers based on the presentations at the 20th annual IEEE conference on computational complexity, San José, CA, USA, June 11–15, 2005. (English) Zbl 1126.68300 Comput. Complexity 15, No. 2, 93-196 (2006). MSC: 68-06 00B25 68Q15 PDFBibTeX XML
Flarup, Uffe; Meer, Klaus Approximation classes for real number optimization problems. (English) Zbl 1126.68675 Calude, C. S. (ed.) et al., Unconventional computation. 5th international conference, UC 2006, York, UK, September 4–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38593-6/pbk). Lecture Notes in Computer Science 4135, 86-100 (2006). MSC: 68W25 68Q15 90C59 90C60 PDFBibTeX XMLCite \textit{U. Flarup} and \textit{K. Meer}, Lect. Notes Comput. Sci. 4135, 86--100 (2006; Zbl 1126.68675) Full Text: DOI
Woods, Damien Optical computing and computational complexity. (English) Zbl 1126.68436 Calude, C. S. (ed.) et al., Unconventional computation. 5th international conference, UC 2006, York, UK, September 4–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38593-6/pbk). Lecture Notes in Computer Science 4135, 27-40 (2006). MSC: 68Q05 68Q10 68Q15 PDFBibTeX XMLCite \textit{D. Woods}, Lect. Notes Comput. Sci. 4135, 27--40 (2006; Zbl 1126.68436) Full Text: DOI
Beame, Paul; Pitassi, Toniann; Segerlind, Nathan; Wigderson, Avi A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. (English) Zbl 1125.68054 Comput. Complexity 15, No. 4, 391-432 (2006). MSC: 68Q15 68Q10 68Q17 PDFBibTeX XMLCite \textit{P. Beame} et al., Comput. Complexity 15, No. 4, 391--432 (2006; Zbl 1125.68054) Full Text: DOI
Kayal, Neeraj; Saxena, Nitin Complexity of ring morphism problems. (English) Zbl 1125.68057 Comput. Complexity 15, No. 4, 342-390 (2006). MSC: 68Q15 13P99 PDFBibTeX XMLCite \textit{N. Kayal} and \textit{N. Saxena}, Comput. Complexity 15, No. 4, 342--390 (2006; Zbl 1125.68057) Full Text: DOI
Shaltiel, Ronen; Umans, Christopher Pseudorandomness for approximate counting and sampling. (English) Zbl 1125.68058 Comput. Complexity 15, No. 4, 298-341 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{R. Shaltiel} and \textit{C. Umans}, Comput. Complexity 15, No. 4, 298--341 (2006; Zbl 1125.68058) Full Text: DOI
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal Computationally private randomizing polynomials and their applications. (English) Zbl 1143.94009 Comput. Complexity 15, No. 2, 115-162 (2006). Reviewer: Jozef Vyskoč (Bratislava) MSC: 94A60 68Q15 PDFBibTeX XMLCite \textit{B. Applebaum} et al., Comput. Complexity 15, No. 2, 115--162 (2006; Zbl 1143.94009) Full Text: DOI
Theobald, Thorsten On the frontiers of polynomial computations in tropical geometry. (English) Zbl 1121.14047 J. Symb. Comput. 41, No. 12, 1360-1375 (2006). MSC: 14P99 68Q17 14Q15 68Q15 68Q25 PDFBibTeX XMLCite \textit{T. Theobald}, J. Symb. Comput. 41, No. 12, 1360--1375 (2006; Zbl 1121.14047) Full Text: DOI arXiv
Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W. The complexity of computing the size of an interval. (English) Zbl 1123.68041 SIAM J. Comput. 36, No. 5, 1264-1300 (2006). MSC: 68Q15 03D15 06A06 68Q05 68Q10 68Q17 PDFBibTeX XMLCite \textit{L. A. Hemaspaandra} et al., SIAM J. Comput. 36, No. 5, 1264--1300 (2006; Zbl 1123.68041) Full Text: DOI
Nguyen, Phuong; Cook, Stephen Theories for TC\(^0\) and other small complexity classes. (English) Zbl 1126.68048 Log. Methods Comput. Sci. 2, No. 1, Paper 3, 39 p. (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{P. Nguyen} and \textit{S. Cook}, Log. Methods Comput. Sci. 2, No. 1, Paper 3, 39 p. (2006; Zbl 1126.68048) Full Text: DOI
Kinsley, A. Anto; Somasundaram, S. Domination based algorithm to \(k\)-center problem. (English) Zbl 1123.05304 J. Discrete Math. Sci. Cryptography 9, No. 3, 403-416 (2006). MSC: 05C69 05C85 68Q15 PDFBibTeX XMLCite \textit{A. A. Kinsley} and \textit{S. Somasundaram}, J. Discrete Math. Sci. Cryptography 9, No. 3, 403--416 (2006; Zbl 1123.05304) Full Text: DOI
Kawachi, Akinori; Yamakami, Tomoyuki Quantum hardcore functions by complexity-theoretical quantum list decoding. (English) Zbl 1133.68344 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-35907-4/pbk). Lecture Notes in Computer Science 4052, 216-227 (2006). MSC: 68Q05 68Q15 81P68 94A60 94B35 PDFBibTeX XMLCite \textit{A. Kawachi} and \textit{T. Yamakami}, Lect. Notes Comput. Sci. 4052, 216--227 (2006; Zbl 1133.68344) Full Text: DOI
Furukawa, Jun; Kurosawa, Kaoru; Imai, Hideki An efficient compiler from \(\Sigma\)-protocol to 2-move deniable zero-knowledge. (English) Zbl 1133.94343 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-35907-4/pbk). Lecture Notes in Computer Science 4052, 46-57 (2006). MSC: 94A62 68Q15 PDFBibTeX XMLCite \textit{J. Furukawa} et al., Lect. Notes Comput. Sci. 4052, 46--57 (2006; Zbl 1133.94343) Full Text: DOI
Vadhan, Salil P. An unconditional study of computational zero knowledge. (English) Zbl 1129.94037 SIAM J. Comput. 36, No. 4, 1160-1214 (2006). Reviewer: Jozef Vyskoč (Bratislava) MSC: 94A60 68Q15 PDFBibTeX XMLCite \textit{S. P. Vadhan}, SIAM J. Comput. 36, No. 4, 1160--1214 (2006; Zbl 1129.94037) Full Text: DOI
Dinur, Irit; Reingold, Omer Assignment testers: Towards a combinatorial proof of the PCP theorem. (English) Zbl 1127.68031 SIAM J. Comput. 36, No. 4, 975-1024 (2006). MSC: 68Q15 68Q17 68R05 68T15 PDFBibTeX XMLCite \textit{I. Dinur} and \textit{O. Reingold}, SIAM J. Comput. 36, No. 4, 975--1024 (2006; Zbl 1127.68031) Full Text: DOI
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal Cryptography in NC\(^0\). (English) Zbl 1126.94014 SIAM J. Comput. 36, No. 4, 845-888 (2006). Reviewer: Vladimír Lacko (Košice) MSC: 94A60 68P25 68Q15 PDFBibTeX XMLCite \textit{B. Applebaum} et al., SIAM J. Comput. 36, No. 4, 845--888 (2006; Zbl 1126.94014) Full Text: DOI
Koiran, Pascal; Perifel, Sylvain Valiant’s model: from exponential sums to exponential products. (English) Zbl 1132.68414 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 596-607 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{P. Koiran} and \textit{S. Perifel}, Lect. Notes Comput. Sci. 4162, 596--607 (2006; Zbl 1132.68414) Full Text: DOI Link
Malod, Guillaume; Portier, Natacha Characterizing Valiant’s algebraic complexity classes. (English) Zbl 1132.68416 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 704-716 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{G. Malod} and \textit{N. Portier}, Lect. Notes Comput. Sci. 4162, 704--716 (2006; Zbl 1132.68416) Full Text: DOI
Spakowski, Holger; Tripathi, Rahul Hierarchical unambiguity. (English) Zbl 1132.68417 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 777-788 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{H. Spakowski} and \textit{R. Tripathi}, Lect. Notes Comput. Sci. 4162, 777--788 (2006; Zbl 1132.68417) Full Text: DOI arXiv
Fortnow, Lance; Ogihara, Mitsunori Very sparse leaf languages. (English) Zbl 1132.68410 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 375-386 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{L. Fortnow} and \textit{M. Ogihara}, Lect. Notes Comput. Sci. 4162, 375--386 (2006; Zbl 1132.68410) Full Text: DOI Link
Le Gall, François Quantum weakly nondeterministic communication complexity. (English) Zbl 1132.68415 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 658-669 (2006). MSC: 68Q15 81P68 PDFBibTeX XMLCite \textit{F. Le Gall}, Lect. Notes Comput. Sci. 4162, 658--669 (2006; Zbl 1132.68415) Full Text: DOI
Lopez-Valdes, Maria Lempel-Ziv dimension for Lempel-Ziv compression. (English) Zbl 1132.68380 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 693-703 (2006). MSC: 68P30 68Q15 PDFBibTeX XMLCite \textit{M. Lopez-Valdes}, Lect. Notes Comput. Sci. 4162, 693--703 (2006; Zbl 1132.68380) Full Text: DOI
Constantinescu, Sorin; Ilie, Lucian The Lempel-Ziv complexity of fixed points of morphisms. (English) Zbl 1132.68516 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 280-291 (2006). MSC: 68R15 68Q15 68P30 PDFBibTeX XMLCite \textit{S. Constantinescu} and \textit{L. Ilie}, Lect. Notes Comput. Sci. 4162, 280--291 (2006; Zbl 1132.68516) Full Text: DOI
Pagourtzis, Aris; Zachos, Stathis The complexity of counting functions with easy decision version. (English) Zbl 1132.68425 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 741-752 (2006). MSC: 68Q25 68Q15 PDFBibTeX XMLCite \textit{A. Pagourtzis} and \textit{S. Zachos}, Lect. Notes Comput. Sci. 4162, 741--752 (2006; Zbl 1132.68425) Full Text: DOI
Gál, Anna; Trifonov, Vladimir On the correlation between parity and modular polynomials. (English) Zbl 1132.68423 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 387-398 (2006). MSC: 68Q25 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Gál} and \textit{V. Trifonov}, Lect. Notes Comput. Sci. 4162, 387--398 (2006; Zbl 1132.68423) Full Text: DOI
Glaßer, Christian; Travers, Stephen Machines that can output empty words. (English) Zbl 1132.68411 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 436-446 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{C. Glaßer} and \textit{S. Travers}, Lect. Notes Comput. Sci. 4162, 436--446 (2006; Zbl 1132.68411) Full Text: DOI
Gu, Xiaoyang; Lutz, Jack H. Dimension characterizations of complexity classes. (English) Zbl 1132.68412 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 471-479 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{X. Gu} and \textit{J. H. Lutz}, Lect. Notes Comput. Sci. 4162, 471--479 (2006; Zbl 1132.68412) Full Text: DOI
Iwama, Kazuo; Morizumi, Hiroki Reductions for monotone Boolean circuits. (English) Zbl 1132.68413 Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2006. 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28–September 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37791-3/pbk). Lecture Notes in Computer Science 4162, 540-548 (2006). MSC: 68Q15 94C10 PDFBibTeX XMLCite \textit{K. Iwama} and \textit{H. Morizumi}, Lect. Notes Comput. Sci. 4162, 540--548 (2006; Zbl 1132.68413) Full Text: DOI
Kleine Büning, Hans; Zhao, Xishun Minimal false quantified Boolean formulas. (English) Zbl 1152.68449 Biere, Armin (ed.) et al., Theory and applications of satisfiability testing – SAT 2006. 9th international conference, Seattle, WA, USA, August 12–15, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37206-7/pbk). Lecture Notes in Computer Science 4121, 339-352 (2006). MSC: 68Q25 03D15 68Q15 68Q17 PDFBibTeX XMLCite \textit{H. Kleine Büning} and \textit{X. Zhao}, Lect. Notes Comput. Sci. 4121, 339--352 (2006; Zbl 1152.68449) Full Text: DOI
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal On pseudorandom generators with linear stretch in NC\(^{0}\). (English) Zbl 1155.94363 Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 260-271 (2006). MSC: 94A60 68Q15 PDFBibTeX XMLCite \textit{B. Applebaum} et al., Lect. Notes Comput. Sci. 4110, 260--271 (2006; Zbl 1155.94363) Full Text: DOI
Healy, Alexander Randomness-efficient sampling within \(\text{NC}^{1}\). (English) Zbl 1155.68391 Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 398-409 (2006). MSC: 68Q15 68W20 PDFBibTeX XMLCite \textit{A. Healy}, Lect. Notes Comput. Sci. 4110, 398--409 (2006; Zbl 1155.68391) Full Text: DOI
Łuczak, Tomasz; Nešetřil, Jaroslav A probabilistic approach to the dichotomy problem. (English) Zbl 1120.68059 SIAM J. Comput. 36, No. 3, 835-843 (2006). MSC: 68Q25 68Q15 68Q17 08A02 05D40 68R05 PDFBibTeX XMLCite \textit{T. Łuczak} and \textit{J. Nešetřil}, SIAM J. Comput. 36, No. 3, 835--843 (2006; Zbl 1120.68059) Full Text: DOI
Beigel, Richard; Fortnow, Lance; Stephan, Frank Infinitely-often autoreducible sets. (English) Zbl 1149.03030 SIAM J. Comput. 36, No. 3, 595-608 (2006). MSC: 03D15 03D30 68Q15 68Q30 PDFBibTeX XMLCite \textit{R. Beigel} et al., SIAM J. Comput. 36, No. 3, 595--608 (2006; Zbl 1149.03030) Full Text: DOI
Diehl, Scott; Van Melkebeek, Dieter Time-space lower bounds for the polynomial-time hierarchy on randomized machines. (English) Zbl 1120.68055 SIAM J. Comput. 36, No. 3, 563-594 (2006). MSC: 68Q17 68Q10 68Q15 PDFBibTeX XMLCite \textit{S. Diehl} and \textit{D. Van Melkebeek}, SIAM J. Comput. 36, No. 3, 563--594 (2006; Zbl 1120.68055) Full Text: DOI
Lacika, Dušan Zero-knowledge protocol based on the subgraph isomorphism problem. (English) Zbl 1165.94322 J. Electr. Eng. 57, No. 7/S, 107-109 (2006). MSC: 94A60 05C90 68Q15 PDFBibTeX XMLCite \textit{D. Lacika}, J. Electr. Eng. 57, No. 7/S, 107--109 (2006; Zbl 1165.94322)
Goldberg, Paul W. A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment. (English) Zbl 1115.68092 SIAM J. Discrete Math. 20, No. 2, 328-343 (2006). MSC: 68Q32 68Q15 52C07 52C35 PDFBibTeX XMLCite \textit{P. W. Goldberg}, SIAM J. Discrete Math. 20, No. 2, 328--343 (2006; Zbl 1115.68092) Full Text: DOI
Beyersdorff, Olaf Disjoint NP-pairs and propositional proof systems. (English) Zbl 1119.03059 Berlin: Humboldt-Univ., Mathematisch-Naturwissenschaftliche Fakultät II (Dissertation). v, 152 p. (2006). MSC: 03F20 03B05 68Q15 68Q17 03F30 68-02 03-02 PDFBibTeX XMLCite \textit{O. Beyersdorff}, Disjoint NP-pairs and propositional proof systems. Berlin: Humboldt-Univ., Mathematisch-Naturwissenschaftliche Fakultät II (Dissertation) (2006; Zbl 1119.03059)
Iwama, Kazuo; Raymond, Rudy; Yamashita, Shigeru Query complexity of quantum biased oracles. (English) Zbl 1116.81016 Imai, Hiroshi (ed.) et al., Quantum computation and information. From theory to experiment. Berlin: Springer (ISBN 3-540-33132-8/hbk). Topics in Applied Physics 102, 19-42 (2006). MSC: 81P68 90C60 68Q15 PDFBibTeX XMLCite \textit{K. Iwama} et al., Top. Appl. Phys. 102, 19--42 (2006; Zbl 1116.81016)
Impagliazzo, Russell; Shaltiel, Ronen; Wigderson, Avi Reducing the seed length in the Nisan-Wigderson generator. (English) Zbl 1121.68052 Combinatorica 26, No. 6, 647-681 (2006). Reviewer: Josef Vyskoc (Rovinka) MSC: 68Q15 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., Combinatorica 26, No. 6, 647--681 (2006; Zbl 1121.68052) Full Text: DOI
Glaßer, Christian; Pavan, A.; Selman, Alan L.; Sengupta, Samik Properties of NP-complete sets. (English) Zbl 1115.68085 SIAM J. Comput. 36, No. 2, 516-542 (2006). MSC: 68Q15 PDFBibTeX XMLCite \textit{C. Glaßer} et al., SIAM J. Comput. 36, No. 2, 516--542 (2006; Zbl 1115.68085) Full Text: DOI
Beyersdorff, Olaf Tuples of disjoint NP-sets. (English) Zbl 1148.68380 Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 80-91 (2006). MSC: 68Q15 03F20 PDFBibTeX XMLCite \textit{O. Beyersdorff}, Lect. Notes Comput. Sci. 3967, 80--91 (2006; Zbl 1148.68380) Full Text: DOI Link
Arvind, V.; Das, Bireswar SZK proofs for black-box group problems. (English) Zbl 1148.68378 Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 6-17 (2006). MSC: 68Q15 20-04 68W20 68W30 PDFBibTeX XMLCite \textit{V. Arvind} and \textit{B. Das}, Lect. Notes Comput. Sci. 3967, 6--17 (2006; Zbl 1148.68378) Full Text: DOI
Friedl, Katalin; Ivanyos, Gábor; Santha, Miklos; Verhoeven, Yves F. Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes. (English) Zbl 1183.68306 Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 6th Italian conference, CIAC 2006, Rome, Italy, May 29–31, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34375-X/pbk). Lecture Notes in Computer Science 3998, 380-391 (2006). MSC: 68Q25 68Q15 68Q17 90C35 PDFBibTeX XMLCite \textit{K. Friedl} et al., Lect. Notes Comput. Sci. 3998, 380--391 (2006; Zbl 1183.68306) Full Text: DOI