×

Found 195 Documents (Results 1–100)

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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

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
Full Text: DOI Link

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite

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
Full Text: arXiv

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

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

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

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI Link

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
Full Text: DOI Link

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite

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

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI Link

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
Full Text: DOI

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
Full Text: DOI arXiv

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
Full Text: DOI Link

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI Link

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 3

Main Field

all top 3

Software