Search dblp for Publications

export results for "toc:db/conf/coco/coco2000.bht:"

 download as .bib file

@inproceedings{DBLP:conf/coco/AmbainisBGKT00,
  author       = {Andris Ambainis and
                  Harry Buhrman and
                  William I. Gasarch and
                  Bala Kalyanasundaram and
                  Leen Torenvliet},
  title        = {The Communication Complexity of Enumeration, Elimination, and Selection},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {44--53},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856734},
  doi          = {10.1109/CCC.2000.856734},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/AmbainisBGKT00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BarringtonKLM00,
  author       = {David A. Mix Barrington and
                  Peter Kadau and
                  Klaus{-}J{\"{o}}rn Lange and
                  Pierre McKenzie},
  title        = {On the Complexity of Some Problems on Groups Input as Multiplication
                  Tables},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {62--69},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856736},
  doi          = {10.1109/CCC.2000.856736},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BarringtonKLM00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BerthiaumeDL00,
  author       = {Andr{\'{e}} Berthiaume and
                  Wim van Dam and
                  Sophie Laplante},
  title        = {Quantum Kolmogorov Complexity},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {240--249},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856755},
  doi          = {10.1109/CCC.2000.856755},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BerthiaumeDL00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BuhrmanLM00,
  author       = {Harry Buhrman and
                  Sophie Laplante and
                  Peter Bro Miltersen},
  title        = {New Bounds for the Language Compression Problem},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {126--130},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856742},
  doi          = {10.1109/CCC.2000.856742},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BuhrmanLM00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Cleve00,
  author       = {Richard Cleve},
  title        = {The Query Complexity of Order-Finding},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {54},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856735},
  doi          = {10.1109/CCC.2000.856735},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Cleve00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/DammHM00,
  author       = {Carsten Damm and
                  Markus Holzer and
                  Pierre McKenzie},
  title        = {The Complexity of Tensor Calculus},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {70--86},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856737},
  doi          = {10.1109/CCC.2000.856737},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/DammHM00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/DurisHI00,
  author       = {Pavol Duris and
                  Juraj Hromkovic and
                  Katsushi Inoue},
  title        = {A Separation of Determinism, Las Vegas and Nondeterminism for Picture
                  Recognition},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {214--228},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856752},
  doi          = {10.1109/CCC.2000.856752},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/DurisHI00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/FortnowM00,
  author       = {Lance Fortnow and
                  Dieter van Melkebeek},
  title        = {Time-Space Tradeoffs for Nondeterministic Computation},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {2--13},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856730},
  doi          = {10.1109/CCC.2000.856730},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/FortnowM00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Giel00,
  author       = {Oliver Giel},
  title        = {BP(L(f)\({}^{\mbox{1+epsilon}}\))},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {36--43},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856733},
  doi          = {10.1109/CCC.2000.856733},
  timestamp    = {Thu, 02 Feb 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Giel00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/GreenHP00,
  author       = {Frederic Green and
                  Steven Homer and
                  Chris Pollett},
  title        = {On the Complexity of Quantum {ACC}},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {250--262},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856756},
  doi          = {10.1109/CCC.2000.856756},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/GreenHP00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/GuruswamiK00,
  author       = {Venkatesan Guruswami and
                  Sanjeev Khanna},
  title        = {On the Hardness of 4-Coloring a 3-Colorable Graph},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {188--197},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856749},
  doi          = {10.1109/CCC.2000.856749},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/GuruswamiK00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/HoangT00,
  author       = {Thanh Minh Hoang and
                  Thomas Thierauf},
  title        = {The Complexity of Verifying the Characteristic Polynomial and Testing
                  Similarity},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {87},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856738},
  doi          = {10.1109/CCC.2000.856738},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/HoangT00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Istrate00,
  author       = {Gabriel Istrate},
  title        = {Computational Complexity and Phase Transitions},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {104--115},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856740},
  doi          = {10.1109/CCC.2000.856740},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Istrate00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/JakobyR00,
  author       = {Andreas Jakoby and
                  R{\"{u}}diger Reischuk},
  title        = {Average Case Complexity of Unbounded Fanin Circuits},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {170},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856748},
  doi          = {10.1109/CCC.2000.856748},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/JakobyR00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Kabanets00,
  author       = {Valentine Kabanets},
  title        = {Easiness Assumptions and Hardness Tests: Trading Time for Zero Error},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {150--157},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856746},
  doi          = {10.1109/CCC.2000.856746},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Kabanets00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/KahnSS00,
  author       = {Jeff Kahn and
                  Michael E. Saks and
                  Cliff Smyth},
  title        = {A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {98--103},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856739},
  doi          = {10.1109/CCC.2000.856739},
  timestamp    = {Wed, 09 Aug 2023 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/conf/coco/KahnSS00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/KarakostasLV00,
  author       = {George Karakostas and
                  Richard J. Lipton and
                  Anastasios Viglas},
  title        = {On the Complexity of Intersecting Finite State Automata},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {229--234},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856753},
  doi          = {10.1109/CCC.2000.856753},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/KarakostasLV00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Kullmann00,
  author       = {Oliver Kullmann},
  title        = {An Application of Matroid Theory to the {SAT} Problem},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {116},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856741},
  doi          = {10.1109/CCC.2000.856741},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Kullmann00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Lutz00,
  author       = {Jack H. Lutz},
  title        = {Dimension in Complexity Classes},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {158--169},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856747},
  doi          = {10.1109/CCC.2000.856747},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Lutz00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/MulmuleyS00,
  author       = {Ketan Mulmuley and
                  Pradyut Shah},
  title        = {A Lower Bound for the Shortest Path Problem},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {14--21},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856731},
  doi          = {10.1109/CCC.2000.856731},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/MulmuleyS00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/RomashchenkoSV00,
  author       = {Andrei E. Romashchenko and
                  Alexander Shen and
                  Nikolai K. Vereshchagin},
  title        = {Combinatorial Interpretation of Kolmogorov Complexity},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {131--137},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856743},
  doi          = {10.1109/CCC.2000.856743},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/RomashchenkoSV00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Schaefer00,
  author       = {Marcus Schaefer},
  title        = {Deciding the K-Dimension is PSPACE-Complete},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {198--203},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856750},
  doi          = {10.1109/CCC.2000.856750},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Schaefer00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Tourlakis00,
  author       = {Iannis Tourlakis},
  title        = {Time-Space Lower Bounds for {SAT} on Uniform and Non-Uniform Machines},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {22},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856732},
  doi          = {10.1109/CCC.2000.856732},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Tourlakis00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Trevisan00,
  author       = {Luca Trevisan},
  title        = {A Survey of Optimal {PCP} Characterizations of {NP}},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {146},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856745},
  doi          = {10.1109/CCC.2000.856745},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Trevisan00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/VereshchaginV00,
  author       = {Nikolai K. Vereshchagin and
                  Michael V. Vyugin},
  title        = {Independent Minimum Length Programs to Translate between Given Strings},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {138},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856744},
  doi          = {10.1109/CCC.2000.856744},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/VereshchaginV00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Vitanyi00,
  author       = {Paul M. B. Vit{\'{a}}nyi},
  title        = {Three Approaches to the Quantitative Definition of Information in
                  an Individual Pure Quantum State},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {263--270},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856757},
  doi          = {10.1109/CCC.2000.856757},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Vitanyi00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Voronenko00,
  author       = {Andrei A. Voronenko},
  title        = {On the Complexity of the Monotonicity Verification},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {235--238},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856754},
  doi          = {10.1109/CCC.2000.856754},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Voronenko00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Wolf00,
  author       = {Ronald de Wolf},
  title        = {Characterization of Non-Deterministic Quantum Query and Quantum Communication
                  Complexity},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {271--278},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856758},
  doi          = {10.1109/CCC.2000.856758},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Wolf00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Yang00,
  author       = {Ke Yang},
  title        = {Integer Circuit Evaluation is PSPACE-Complete},
  booktitle    = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  pages        = {204},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://doi.org/10.1109/CCC.2000.856751},
  doi          = {10.1109/CCC.2000.856751},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Yang00.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@proceedings{DBLP:conf/coco/2000,
  title        = {Proceedings of the 15th Annual {IEEE} Conference on Computational
                  Complexity, Florence, Italy, July 4-7, 2000},
  publisher    = {{IEEE} Computer Society},
  year         = {2000},
  url          = {https://ieeexplore.ieee.org/xpl/conhome/6911/proceeding},
  isbn         = {0-7695-0674-7},
  timestamp    = {Thu, 02 Feb 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/2000.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}
a service of  Schloss Dagstuhl - Leibniz Center for Informatics

manage site settings

To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.