default search action
Search dblp for Publications
export results for "toc:db/conf/coco/coco2001.bht:"
@inproceedings{DBLP:conf/coco/Agrawal01, author = {Manindra Agrawal}, title = {Towards Uniform AC\({}^{\mbox{0}}\) - Isomorphisms}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {13--20}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933866}, doi = {10.1109/CCC.2001.933866}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Agrawal01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AllenderBH01, author = {Eric Allender and David A. Mix Barrington and William Hesse}, title = {Uniform Circuits for Division: Consequences and Problems}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {150--159}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933882}, doi = {10.1109/CCC.2001.933882}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AllenderBH01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AllenderKRRV01, author = {Eric Allender and Michal Kouck{\'{y}} and Detlef Ronneburger and Sambuddha Roy and V. Vinay}, title = {Time-Space Tradeoffs in the Counting Hierarchy}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {295--302}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933896}, doi = {10.1109/CCC.2001.933896}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AllenderKRRV01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AlonB01, author = {Noga Alon and Richard Beigel}, title = {Lower Bounds for Approximations by Low Degree Polynomials Over Z\({}_{\mbox{m}}\)}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {184--187}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933885}, doi = {10.1109/CCC.2001.933885}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AlonB01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Ambos-SpiesMRS01, author = {Klaus Ambos{-}Spies and Wolfgang Merkle and Jan Reimann and Frank Stephan}, title = {Hausdorff Dimension in Exponential Time}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {210--217}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933888}, doi = {10.1109/CCC.2001.933888}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Ambos-SpiesMRS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AntunesFM01, author = {Luis Antunes and Lance Fortnow and Dieter van Melkebeek}, title = {Computational Depth}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {266--273}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933893}, doi = {10.1109/CCC.2001.933893}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AntunesFM01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AtseriasGP01, author = {Albert Atserias and Nicola Galesi and Pavel Pudl{\'{a}}k}, title = {Monotone Simulations of Nonmonotone Proofs}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {36--41}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933870}, doi = {10.1109/CCC.2001.933870}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AtseriasGP01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/BeameIS01, author = {Paul Beame and Russell Impagliazzo and Ashish Sabharwal}, title = {Resolution Complexity of Independent Sets in Random Graphs}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {52--68}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933872}, doi = {10.1109/CCC.2001.933872}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/coco/BeameIS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/BeimelI01, author = {Amos Beimel and Yuval Ishai}, title = {On the Power of Nonlinear Secrect-Sharing}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {188--202}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933886}, doi = {10.1109/CCC.2001.933886}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/BeimelI01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Ben-SassonG01, author = {Eli Ben{-}Sasson and Nicola Galesi}, title = {Space Complexity of Random Formulae in Resolution}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {42--51}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933871}, doi = {10.1109/CCC.2001.933871}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Ben-SassonG01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/BolligSW01, author = {Beate Bollig and Martin Sauerhoff and Ingo Wegener}, title = {On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {172--183}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933884}, doi = {10.1109/CCC.2001.933884}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/BolligSW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/BuhrmanDHHMSW01, author = {Harry Buhrman and Christoph D{\"{u}}rr and Mark Heiligman and Peter H{\o}yer and Fr{\'{e}}d{\'{e}}ric Magniez and Miklos Santha and Ronald de Wolf}, title = {Quantum Algorithms for Element Distinctness}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {131--137}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933880}, doi = {10.1109/CCC.2001.933880}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/BuhrmanDHHMSW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/BuhrmanW01, author = {Harry Buhrman and Ronald de Wolf}, title = {Communication Complexity Lower Bounds by Polynomials}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {120--130}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933879}, doi = {10.1109/CCC.2001.933879}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/BuhrmanW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/ChangS01, author = {Richard Chang and Jon S. Squire}, title = {Bounded Query Functions with Limited Output Bits}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {90--98}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933876}, doi = {10.1109/CCC.2001.933876}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/ChangS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Dai01, author = {Jack Jie Dai}, title = {A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {204--209}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933887}, doi = {10.1109/CCC.2001.933887}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Dai01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/DantchevR01, author = {Stefan S. Dantchev and S{\o}ren Riis}, title = {Tree Resolution Proofs of the Weak Pigeon-Hole Principle}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {69--75}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933873}, doi = {10.1109/CCC.2001.933873}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/DantchevR01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Forster01, author = {J{\"{u}}rgen Forster}, title = {A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {100--106}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933877}, doi = {10.1109/CCC.2001.933877}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Forster01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Fortnow01, author = {Lance Fortnow}, title = {Comparing Notions of Full Derandomization}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {28--34}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933869}, doi = {10.1109/CCC.2001.933869}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Fortnow01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Gacs01, author = {P{\'{e}}ter G{\'{a}}cs}, title = {Quantum Algorithmic Entropy}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {274--283}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933894}, doi = {10.1109/CCC.2001.933894}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Gacs01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/HastadW01, author = {Johan H{\aa}stad and Avi Wigderson}, title = {Simple Analysis of Graph Tests for Linearity and {PCP}}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {244--254}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933891}, doi = {10.1109/CCC.2001.933891}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/HastadW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/ImpagliazzoKW01, author = {Russell Impagliazzo and Valentine Kabanets and Avi Wigderson}, title = {In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {2--12}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933865}, doi = {10.1109/CCC.2001.933865}, timestamp = {Tue, 07 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/coco/ImpagliazzoKW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Koucky01, author = {Michal Kouck{\'{y}}}, title = {Universal Traversal Sequences with Backtracking}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {21--27}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933868}, doi = {10.1109/CCC.2001.933868}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Koucky01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/MosselU01, author = {Elchanan Mossel and Christopher Umans}, title = {On the Complexity of Approximating the {VC} Dimension}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {220--225}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933889}, doi = {10.1109/CCC.2001.933889}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/MosselU01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/MuchnikV01, author = {Andrei A. Muchnik and Nikolai K. Vereshchagin}, title = {Logical Operations and Kolmogorov Complexity {II}}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {256--265}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933892}, doi = {10.1109/CCC.2001.933892}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/MuchnikV01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/PavanS01, author = {Aduri Pavan and Alan L. Selman}, title = {Separation of NP-Completeness Notions}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {78--89}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933875}, doi = {10.1109/CCC.2001.933875}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/PavanS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Santhanam01, author = {Rahul Santhanam}, title = {On Separators, Segregators and Time versus Space}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {286--294}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933895}, doi = {10.1109/CCC.2001.933895}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Santhanam01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/ServedioG01, author = {Rocco A. Servedio and Steven J. Gortler}, title = {Quantum versus Classical Learnability}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {138--148}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933881}, doi = {10.1109/CCC.2001.933881}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/ServedioG01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Shaltiel01, author = {Ronen Shaltiel}, title = {Towards Proving Strong Direct Product Theorems}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {107--117}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933878}, doi = {10.1109/CCC.2001.933878}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/Shaltiel01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/Shpilka01, author = {Amir Shpilka}, title = {Affine Projections of Symmetric Polynomials}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {160--171}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933883}, doi = {10.1109/CCC.2001.933883}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/coco/Shpilka01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/StockmeyerM01, author = {Larry J. Stockmeyer and Dharmendra S. Modha}, title = {Links Between Complexity Theory and Constrained Block Coding}, booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, pages = {226--243}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://doi.org/10.1109/CCC.2001.933890}, doi = {10.1109/CCC.2001.933890}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/StockmeyerM01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@proceedings{DBLP:conf/coco/2001, title = {Proceedings of the 16th Annual {IEEE} Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}, publisher = {{IEEE} Computer Society}, year = {2001}, url = {https://ieeexplore.ieee.org/xpl/conhome/7429/proceeding}, isbn = {0-7695-1053-1}, timestamp = {Thu, 02 Feb 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/2001.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
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.