Search dblp for Publications

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

 download as .bib file

@inproceedings{DBLP:conf/coco/AllenderW88,
  author       = {Eric Allender and
                  Osamu Watanabe},
  title        = {Kolmogorov complexity and degrees of tally sets},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {102--111},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5269},
  doi          = {10.1109/SCT.1988.5269},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/AllenderW88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Balcazar88,
  author       = {Jos{\'{e}} L. Balc{\'{a}}zar},
  title        = {Logspace self-reducibility},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {40--46},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5261},
  doi          = {10.1109/SCT.1988.5261},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Balcazar88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BarringtonIS88,
  author       = {David A. Mix Barrington and
                  Neil Immerman and
                  Howard Straubing},
  title        = {On uniformity within NC\({}^{\mbox{1}}\)},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {47--59},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5262},
  doi          = {10.1109/SCT.1988.5262},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BarringtonIS88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BookDR88,
  author       = {Ronald V. Book and
                  Ding{-}Zhu Du and
                  David A. Russo},
  title        = {On polynomial and generalized complexity cores},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {236--250},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5283},
  doi          = {10.1109/SCT.1988.5283},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BookDR88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Borodin88,
  author       = {Allan Borodin},
  title        = {Juris Hartmanis: building a department-building a discipline},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {135--137},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5273},
  doi          = {10.1109/SCT.1988.5273},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Borodin88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BorodinCDRT88,
  author       = {Allan Borodin and
                  Stephen A. Cook and
                  Patrick W. Dymond and
                  Walter L. Ruzzo and
                  Martin Tompa},
  title        = {Two applications of complementation via inductive counting},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {116--125},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5271},
  doi          = {10.1109/SCT.1988.5271},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BorodinCDRT88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/BussH88,
  author       = {Samuel R. Buss and
                  Louise Hay},
  title        = {On truth-table reducibility to {SAT} and the difference hierarchy
                  over {NP}},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {224--233},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5282},
  doi          = {10.1109/SCT.1988.5282},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/BussH88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/CaiH88,
  author       = {Jin{-}Yi Cai and
                  Lane A. Hemachandra},
  title        = {Enumerative counting is hard},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {194--203},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5279},
  doi          = {10.1109/SCT.1988.5279},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/CaiH88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Condon88,
  author       = {Anne Condon},
  title        = {Space bounded probabilistic game automata},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {162--174},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5276},
  doi          = {10.1109/SCT.1988.5276},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Condon88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/FortnowRS88,
  author       = {Lance Fortnow and
                  John Rompel and
                  Michael Sipser},
  title        = {On the power of multi-power interactive protocols},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {156--161},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5275},
  doi          = {10.1109/SCT.1988.5275},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/FortnowRS88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/HalstenbergR88,
  author       = {Bernd Halstenberg and
                  R{\"{u}}diger Reischuk},
  title        = {Relations between communication complexity classes},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {19--28},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5259},
  doi          = {10.1109/SCT.1988.5259},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/HalstenbergR88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Huynh88,
  author       = {Dung T. Huynh},
  title        = {The complexity of ranking},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {204--212},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5280},
  doi          = {10.1109/SCT.1988.5280},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Huynh88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/IbarraJ88,
  author       = {Oscar H. Ibarra and
                  Tao Jiang},
  title        = {Trading reversals for alternation},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {70--77},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5264},
  doi          = {10.1109/SCT.1988.5264},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/IbarraJ88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Immerman88,
  author       = {Neil Immerman},
  title        = {Nondeterministic space is closed under complementation},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {112--115},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5270},
  doi          = {10.1109/SCT.1988.5270},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Immerman88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/ImpagliazzoN88,
  author       = {Russell Impagliazzo and
                  Moni Naor},
  title        = {Decision trees and downward closures},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {29--38},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5260},
  doi          = {10.1109/SCT.1988.5260},
  timestamp    = {Sat, 30 Sep 2023 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/conf/coco/ImpagliazzoN88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Kadin88,
  author       = {Jim Kadin},
  title        = {The polynomial time hierarchy collapses if the Boolean hierarchy collapses},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {278--292},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5287},
  doi          = {10.1109/SCT.1988.5287},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Kadin88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Ko88,
  author       = {Ker{-}I Ko},
  title        = {Relativized polynomial time hierarchies having exactly {K} levels},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5284},
  doi          = {10.1109/SCT.1988.5284},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Ko88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Ko88a,
  author       = {Ker{-}I Ko},
  title        = {Distinguishing bounded reducibilities by sparse sets},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {181--191},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5278},
  doi          = {10.1109/SCT.1988.5278},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Ko88a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/LiV88,
  author       = {Ming Li and
                  Paul M. B. Vit{\'{a}}nyi},
  title        = {Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich
                  Kolmogorov 1903-87},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {80--101},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5265},
  doi          = {10.1109/SCT.1988.5265},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/LiV88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/LongpreY88,
  author       = {Luc Longpr{\'{e}} and
                  Paul Young},
  title        = {Cook is faster than Karp: a study of reducibilities in {NP}},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {293--302},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5288},
  doi          = {10.1109/SCT.1988.5288},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/LongpreY88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Lutz88,
  author       = {Jack H. Lutz},
  title        = {Pseudorandom sources for {BPP}},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {175--180},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5277},
  doi          = {10.1109/SCT.1988.5277},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Lutz88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/PittW88,
  author       = {Leonard Pitt and
                  Manfred K. Warmuth},
  title        = {Reductions among prediction problems: on the difficulty of predicting
                  automata},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {60--69},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5263},
  doi          = {10.1109/SCT.1988.5263},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/PittW88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Schoning88,
  author       = {Uwe Sch{\"{o}}ning},
  title        = {The power of counting},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {2--9},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5257},
  doi          = {10.1109/SCT.1988.5257},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Schoning88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/ShinodaS88,
  author       = {Juichi Shinoda and
                  Theodore A. Slaman},
  title        = {On the theory of the {PTIME} degrees of the recursive sets},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {252--257},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5285},
  doi          = {10.1109/SCT.1988.5285},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/ShinodaS88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Stearns88,
  author       = {Richard Edwin Stearns},
  title        = {Juris Hartmanis: the beginnings of computational complexity},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {128--134},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5272},
  doi          = {10.1109/SCT.1988.5272},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Stearns88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/TangW88,
  author       = {Shouwen Tang and
                  Osamu Watanabe},
  title        = {On tally relativizations of BP-complexity classes},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {10--18},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5258},
  doi          = {10.1109/SCT.1988.5258},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/TangW88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Toran88,
  author       = {Jacobo Tor{\'{a}}n},
  title        = {An oracle characterization of the counting hierarchy},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {213--223},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5281},
  doi          = {10.1109/SCT.1988.5281},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Toran88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Wagner88,
  author       = {Klaus W. Wagner},
  title        = {Bounded query computations},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {260--277},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5286},
  doi          = {10.1109/SCT.1988.5286},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Wagner88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{DBLP:conf/coco/Young88,
  author       = {Paul Young},
  title        = {Juris Hartmanis: fundamental contributions to isomorphism problems},
  booktitle    = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  pages        = {138--154},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://doi.org/10.1109/SCT.1988.5274},
  doi          = {10.1109/SCT.1988.5274},
  timestamp    = {Fri, 24 Mar 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/Young88.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@proceedings{DBLP:conf/coco/1988,
  title        = {Proceedings: Third Annual Structure in Complexity Theory Conference,
                  Georgetown University, Washington, D. C., USA, June 14-17, 1988},
  publisher    = {{IEEE} Computer Society},
  year         = {1988},
  url          = {https://ieeexplore.ieee.org/xpl/conhome/209/proceeding},
  isbn         = {0-8186-0794-7},
  timestamp    = {Thu, 02 Feb 2023 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/conf/coco/1988.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.