default search action
BibTeX records: Michael Sipser
@article{DBLP:journals/eccc/RemscrimS13,
author = {Zachary Remscrim and
Michael Sipser},
title = {AC\({}^{\mbox{0}}\) Pseudorandomness of Natural Operations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-088}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/088},
eprinttype = {ECCC},
eprint = {TR13-088},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/RemscrimS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/tmfcs/2008,
editor = {Zoran Majkic and
Michael Sipser and
R. Radha and
Daming Wei},
title = {International Conference on Theoretical and Mathematical Foundations
of Computer Science, TMFCS-08, Orlando, Florida, USA, July 7-10, 2008},
publisher = {{ISRST}},
year = {2008},
isbn = {978-1-60651-006-3},
timestamp = {Mon, 18 Aug 2008 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tmfcs/2008.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-DM-0101028,
author = {Ming{-}Yang Kao and
Yuan Ma and
Michael Sipser and
Yiqun Lisa Yin},
title = {Optimal Constructions of Hybrid Algorithms},
journal = {CoRR},
volume = {cs.DM/0101028},
year = {2001},
url = {https://arxiv.org/abs/cs/0101028},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-DM-0101028.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/KaoMSY98,
author = {Ming{-}Yang Kao and
Yuan Ma and
Michael Sipser and
Yiqun Lisa Yin},
title = {Optimal Constructions of Hybrid Algorithms},
journal = {J. Algorithms},
volume = {29},
number = {1},
pages = {142--164},
year = {1998},
url = {https://doi.org/10.1006/jagm.1998.0959},
doi = {10.1006/JAGM.1998.0959},
timestamp = {Fri, 13 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/KaoMSY98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/daglib/0086373,
author = {Michael Sipser},
title = {Introduction to the theory of computation},
publisher = {{PWS} Publishing Company},
year = {1997},
isbn = {978-0-534-94728-6},
timestamp = {Thu, 21 Apr 2011 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/daglib/0086373.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FortnowS97,
author = {Lance Fortnow and
Michael Sipser},
title = {Retraction of Probabilistic Computation and Linear Time},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory
of Computing, El Paso, Texas, USA, May 4-6, 1997},
pages = {750},
year = {1997},
crossref = {DBLP:conf/stoc/1997},
url = {https://doi.org/10.1145/258533.258677},
doi = {10.1145/258533.258677},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/FortnowS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/Sipser96,
author = {Michael Sipser},
title = {Introduction to the Theory of Computation},
journal = {{SIGACT} News},
volume = {27},
number = {1},
pages = {27--29},
year = {1996},
url = {https://doi.org/10.1145/230514.571645},
doi = {10.1145/230514.571645},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Sipser96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/PapadimitriouGWRS96,
author = {Christos H. Papadimitriou and
Oded Goldreich and
Avi Wigderson and
Alexander A. Razborov and
Michael Sipser},
title = {The future of computational complexity theory: part {I}},
journal = {{SIGACT} News},
volume = {27},
number = {3},
pages = {6--12},
year = {1996},
url = {https://doi.org/10.1145/235666.235668},
doi = {10.1145/235666.235668},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/PapadimitriouGWRS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/SipserS96,
author = {Michael Sipser and
Daniel A. Spielman},
title = {Expander codes},
journal = {{IEEE} Trans. Inf. Theory},
volume = {42},
number = {6},
pages = {1710--1722},
year = {1996},
url = {https://doi.org/10.1109/18.556667},
doi = {10.1109/18.556667},
timestamp = {Mon, 26 Oct 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/SipserS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/GrigniS95,
author = {Michelangelo Grigni and
Michael Sipser},
title = {Monotone Separation of Logarithmic Space from Logarithmic Depth},
journal = {J. Comput. Syst. Sci.},
volume = {50},
number = {3},
pages = {433--437},
year = {1995},
url = {https://doi.org/10.1006/jcss.1995.1033},
doi = {10.1006/JCSS.1995.1033},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/GrigniS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/FortnowRS94,
author = {Lance Fortnow and
John Rompel and
Michael Sipser},
title = {On the Power of Multi-Prover Interactive Protocols},
journal = {Theor. Comput. Sci.},
volume = {134},
number = {2},
pages = {545--557},
year = {1994},
url = {https://doi.org/10.1016/0304-3975(94)90251-8},
doi = {10.1016/0304-3975(94)90251-8},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/FortnowRS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/GillmanS94,
author = {David Gillman and
Michael Sipser},
title = {Inference and Minimization of Hidden Markov Chains},
booktitle = {Proceedings of the Seventh Annual {ACM} Conference on Computational
Learning Theory, {COLT} 1994, New Brunswick, NJ, USA, July 12-15,
1994},
pages = {147--158},
year = {1994},
crossref = {DBLP:conf/colt/1994},
url = {https://doi.org/10.1145/180139.181091},
doi = {10.1145/180139.181091},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/GillmanS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SipserS94,
author = {Michael Sipser and
Daniel A. Spielman},
title = {Expander Codes},
booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
New Mexico, USA, November 20-22, 1994},
pages = {566--576},
year = {1994},
crossref = {DBLP:conf/focs/FOCS35},
url = {https://doi.org/10.1109/SFCS.1994.365734},
doi = {10.1109/SFCS.1994.365734},
timestamp = {Sun, 02 Nov 2025 21:27:17 +0100},
biburl = {https://dblp.org/rec/conf/focs/SipserS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaoMSY94,
author = {Ming{-}Yang Kao and
Yuan Ma and
Michael Sipser and
Yiqun Lisa Yin},
title = {Optimal Constructions of Hybrid Algorithms},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {372--381},
year = {1994},
crossref = {DBLP:conf/soda/1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314572},
timestamp = {Thu, 05 Jul 2018 07:29:19 +0200},
biburl = {https://dblp.org/rec/conf/soda/KaoMSY94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sipser92,
author = {Michael Sipser},
title = {The History and Status of the {P} versus {NP} Question},
booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
pages = {603--618},
year = {1992},
crossref = {DBLP:conf/stoc/STOC24},
url = {https://doi.org/10.1145/129712.129771},
doi = {10.1145/129712.129771},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sipser92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GoldbergS91,
author = {Andrew V. Goldberg and
Michael Sipser},
title = {Compression and Ranking},
journal = {{SIAM} J. Comput.},
volume = {20},
number = {3},
pages = {524--536},
year = {1991},
url = {https://doi.org/10.1137/0220034},
doi = {10.1137/0220034},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GoldbergS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GrigniS91,
author = {Michelangelo Grigni and
Michael Sipser},
title = {Monotone Separation of Logspace from {NC}},
booktitle = {Proceedings of the Sixth Annual Structure in Complexity Theory Conference,
Chicago, Illinois, USA, June 30 - July 3, 1991},
pages = {294--298},
year = {1991},
crossref = {DBLP:conf/coco/1991},
url = {https://doi.org/10.1109/SCT.1991.160272},
doi = {10.1109/SCT.1991.160272},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/GrigniS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/FortnowRS90,
author = {Lance Fortnow and
John Rompel and
Michael Sipser},
title = {Errata for On the Power of Multi-Prover Interactive Protocols},
booktitle = {Proceedings: Fifth Annual Structure in Complexity Theory Conference,
Universitat Polit{\`{e}}cnica de Catalunya, Barcelona, Spain, July
8-11, 1990},
pages = {318--319},
year = {1990},
crossref = {DBLP:conf/coco/1990},
timestamp = {Thu, 02 Feb 2023 13:27:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/FortnowRS90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:books/el/leeuwen90/BoppanaS90,
author = {Ravi B. Boppana and
Michael Sipser},
title = {The Complexity of Finite Functions},
booktitle = {Handbook of Theoretical Computer Science, Volume {A:} Algorithms and
Complexity},
pages = {757--804},
year = {1990},
crossref = {DBLP:books/el/Leeuwen90},
timestamp = {Sat, 03 Aug 2019 19:26:43 +0200},
biburl = {https://dblp.org/rec/books/el/leeuwen90/BoppanaS90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/acr/GoldwasserS89,
author = {Shafi Goldwasser and
Michael Sipser},
title = {Private Coins versus Public Coins in Interactive Proof Systems},
journal = {Adv. Comput. Res.},
volume = {5},
pages = {73--90},
year = {1989},
timestamp = {Tue, 25 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/acr/GoldwasserS89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/acr/FurerGMSZ89,
author = {Martin F{\"{u}}rer and
Oded Goldreich and
Yishay Mansour and
Michael Sipser and
Stathis Zachos},
title = {On Completeness and Soundness in Interactive Proof Systems},
journal = {Adv. Comput. Res.},
volume = {5},
pages = {429--442},
year = {1989},
timestamp = {Tue, 25 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/acr/FurerGMSZ89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/FortnowS88,
author = {Lance Fortnow and
Michael Sipser},
title = {Are There Interactive Protocols for {CO-NP} Languages?},
journal = {Inf. Process. Lett.},
volume = {28},
number = {5},
pages = {249--251},
year = {1988},
url = {https://doi.org/10.1016/0020-0190(88)90199-8},
doi = {10.1016/0020-0190(88)90199-8},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/FortnowS88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Sipser88,
author = {Michael Sipser},
title = {Expanders, Randomness, or Time versus Space},
journal = {J. Comput. Syst. Sci.},
volume = {36},
number = {3},
pages = {379--383},
year = {1988},
url = {https://doi.org/10.1016/0022-0000(88)90035-9},
doi = {10.1016/0022-0000(88)90035-9},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Sipser88.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},
year = {1988},
crossref = {DBLP:conf/coco/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/focs/AwerbuchS88,
author = {Baruch Awerbuch and
Michael Sipser},
title = {Dynamic Networks Are as Fast as Static Networks (Preliminary Version)},
booktitle = {29th Annual Symposium on Foundations of Computer Science, White Plains,
New York, USA, 24-26 October 1988},
pages = {206--220},
year = {1988},
crossref = {DBLP:conf/focs/FOCS29},
url = {https://doi.org/10.1109/SFCS.1988.21938},
doi = {10.1109/SFCS.1988.21938},
timestamp = {Tue, 08 Jul 2025 16:47:01 +0200},
biburl = {https://dblp.org/rec/conf/focs/AwerbuchS88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/BuiCLS87,
author = {Thang Nguyen Bui and
Soma Chaudhuri and
Frank Thomson Leighton and
Michael Sipser},
title = {Graph bisection algorithms with good average case behavior},
journal = {Comb.},
volume = {7},
number = {2},
pages = {171--191},
year = {1987},
url = {https://doi.org/10.1007/BF02579448},
doi = {10.1007/BF02579448},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/BuiCLS87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GoldreichMS87,
author = {Oded Goldreich and
Yishay Mansour and
Michael Sipser},
title = {Interactive Proof Systems: Provers that never Fail and Random Selection
(Extended Abstract)},
booktitle = {28th Annual Symposium on Foundations of Computer Science, Los Angeles,
California, USA, 27-29 October 1987},
pages = {449--461},
year = {1987},
crossref = {DBLP:conf/focs/FOCS28},
url = {https://doi.org/10.1109/SFCS.1987.35},
doi = {10.1109/SFCS.1987.35},
timestamp = {Tue, 08 Jul 2025 16:47:17 +0200},
biburl = {https://dblp.org/rec/conf/focs/GoldreichMS87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Sipser86,
author = {Michael Sipser},
title = {Expanders, Randomness, or Time versus Space},
booktitle = {Structure in Complexity Theory, Proceedings of the Conference hold
at the University of California, Berkeley, California, USA, June 2-5,
1986},
pages = {325--329},
year = {1986},
crossref = {DBLP:conf/coco/1986},
url = {https://doi.org/10.1007/3-540-16486-3\_108},
doi = {10.1007/3-540-16486-3\_108},
timestamp = {Thu, 02 Feb 2023 13:27:01 +0100},
biburl = {https://dblp.org/rec/conf/coco/Sipser86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldwasserS86,
author = {Shafi Goldwasser and
Michael Sipser},
title = {Private Coins versus Public Coins in Interactive Proof Systems},
booktitle = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA}},
pages = {59--68},
year = {1986},
crossref = {DBLP:conf/stoc/STOC18},
url = {https://doi.org/10.1145/12130.12137},
doi = {10.1145/12130.12137},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldwasserS86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldbergS85,
author = {Andrew V. Goldberg and
Michael Sipser},
title = {Compression and Ranking},
booktitle = {Proceedings of the 17th Annual {ACM} Symposium on Theory of Computing,
May 6-8, 1985, Providence, Rhode Island, {USA}},
pages = {440--448},
year = {1985},
crossref = {DBLP:conf/stoc/STOC17},
url = {https://doi.org/10.1145/22145.22194},
doi = {10.1145/22145.22194},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldbergS85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ior/SimonsS84,
author = {Barbara Simons and
Michael Sipser},
title = {On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline
Intervals},
journal = {Oper. Res.},
volume = {32},
number = {1},
pages = {80--88},
year = {1984},
url = {https://doi.org/10.1287/opre.32.1.80},
doi = {10.1287/OPRE.32.1.80},
timestamp = {Tue, 31 Mar 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/SimonsS84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/PapadimitriouS84,
author = {Christos H. Papadimitriou and
Michael Sipser},
title = {Communication Complexity},
journal = {J. Comput. Syst. Sci.},
volume = {28},
number = {2},
pages = {260--269},
year = {1984},
url = {https://doi.org/10.1016/0022-0000(84)90069-2},
doi = {10.1016/0022-0000(84)90069-2},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/PapadimitriouS84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/FurstSS84,
author = {Merrick L. Furst and
James B. Saxe and
Michael Sipser},
title = {Parity, Circuits, and the Polynomial-Time Hierarchy},
journal = {Math. Syst. Theory},
volume = {17},
number = {1},
pages = {13--27},
year = {1984},
url = {https://doi.org/10.1007/BF01744431},
doi = {10.1007/BF01744431},
timestamp = {Sun, 17 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/FurstSS84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BuiCLS84,
author = {Thang Nguyen Bui and
Soma Chaudhuri and
Frank Thomson Leighton and
Michael Sipser},
title = {Graph Bisection Algorithms with Good Average Case Behavior},
booktitle = {25th Annual Symposium on Foundations of Computer Science, West Palm
Beach, Florida, USA, 24-26 October 1984},
pages = {181--192},
year = {1984},
crossref = {DBLP:conf/focs/FOCS25},
url = {https://doi.org/10.1109/SFCS.1984.715914},
doi = {10.1109/SFCS.1984.715914},
timestamp = {Tue, 08 Jul 2025 16:49:11 +0200},
biburl = {https://dblp.org/rec/conf/focs/BuiCLS84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/Sipser84,
author = {Michael Sipser},
title = {A Topological View of Some Problems in Complexity Theory},
booktitle = {Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia,
September 3-7, 1984, Proceedings},
pages = {567--572},
year = {1984},
crossref = {DBLP:conf/mfcs/1984},
url = {https://doi.org/10.1007/BFb0030341},
doi = {10.1007/BFB0030341},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/Sipser84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sipser83,
author = {Michael Sipser},
title = {Borel Sets and Circuit Complexity},
booktitle = {Proceedings of the 15th Annual {ACM} Symposium on Theory of Computing,
25-27 April, 1983, Boston, Massachusetts, {USA}},
pages = {61--69},
year = {1983},
crossref = {DBLP:conf/stoc/STOC15},
url = {https://doi.org/10.1145/800061.808733},
doi = {10.1145/800061.808733},
timestamp = {Mon, 26 May 2025 08:18:30 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Sipser83.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sipser83a,
author = {Michael Sipser},
title = {A Complexity Theoretic Approach to Randomness},
booktitle = {Proceedings of the 15th Annual {ACM} Symposium on Theory of Computing,
25-27 April, 1983, Boston, Massachusetts, {USA}},
pages = {330--335},
year = {1983},
crossref = {DBLP:conf/stoc/STOC15},
url = {https://doi.org/10.1145/800061.808762},
doi = {10.1145/800061.808762},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sipser83a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Sipser82,
author = {Michael Sipser},
title = {On Relativization and the Existence of Complete Sets},
booktitle = {Automata, Languages and Programming, 9th Colloquium, Aarhus, Denmark,
July 12-16, 1982, Proceedings},
pages = {523--531},
year = {1982},
crossref = {DBLP:conf/icalp/1982},
url = {https://doi.org/10.1007/BFb0012797},
doi = {10.1007/BFB0012797},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Sipser82.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/PapadimitriouS82,
author = {Christos H. Papadimitriou and
Michael Sipser},
title = {Communication Complexity},
booktitle = {Proceedings of the 14th Annual {ACM} Symposium on Theory of Computing,
May 5-7, 1982, San Francisco, California, {USA}},
pages = {196--200},
year = {1982},
crossref = {DBLP:conf/stoc/STOC14},
url = {https://doi.org/10.1145/800070.802192},
doi = {10.1145/800070.802192},
timestamp = {Wed, 14 Nov 2018 10:51:38 +0100},
biburl = {https://dblp.org/rec/conf/stoc/PapadimitriouS82.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/KatseffS81,
author = {Howard P. Katseff and
Michael Sipser},
title = {Several Results in Program Size Complexity},
journal = {Theor. Comput. Sci.},
volume = {15},
pages = {291--309},
year = {1981},
url = {https://doi.org/10.1016/0304-3975(81)90083-9},
doi = {10.1016/0304-3975(81)90083-9},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/KatseffS81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FurstSS81,
author = {Merrick L. Furst and
James B. Saxe and
Michael Sipser},
title = {Parity, Circuits, and the Polynomial-Time Hierarchy},
booktitle = {22nd Annual Symposium on Foundations of Computer Science, Nashville,
Tennessee, USA, 28-30 October 1981},
pages = {260--270},
year = {1981},
crossref = {DBLP:conf/focs/FOCS22},
url = {https://doi.org/10.1109/SFCS.1981.35},
doi = {10.1109/SFCS.1981.35},
timestamp = {Tue, 08 Jul 2025 16:49:53 +0200},
biburl = {https://dblp.org/rec/conf/focs/FurstSS81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KarpS81,
author = {Richard M. Karp and
Michael Sipser},
title = {Maximum Matchings in Sparse Random Graphs},
booktitle = {22nd Annual Symposium on Foundations of Computer Science, Nashville,
Tennessee, USA, 28-30 October 1981},
pages = {364--375},
year = {1981},
crossref = {DBLP:conf/focs/FOCS22},
url = {https://doi.org/10.1109/SFCS.1981.21},
doi = {10.1109/SFCS.1981.21},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KarpS81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/LichtensteinS80,
author = {David Lichtenstein and
Michael Sipser},
title = {{GO} Is Polynomial-Space Hard},
journal = {J. {ACM}},
volume = {27},
number = {2},
pages = {393--401},
year = {1980},
url = {https://doi.org/10.1145/322186.322201},
doi = {10.1145/322186.322201},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/LichtensteinS80.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Sipser80,
author = {Michael Sipser},
title = {Lower Bounds on the Size of Sweeping Automata},
journal = {J. Comput. Syst. Sci.},
volume = {21},
number = {2},
pages = {195--202},
year = {1980},
url = {https://doi.org/10.1016/0022-0000(80)90034-3},
doi = {10.1016/0022-0000(80)90034-3},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Sipser80.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Sipser80,
author = {Michael Sipser},
title = {Halting Space-Bounded Computations},
journal = {Theor. Comput. Sci.},
volume = {10},
pages = {335--338},
year = {1980},
url = {https://doi.org/10.1016/0304-3975(80)90053-5},
doi = {10.1016/0304-3975(80)90053-5},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Sipser80.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Sipser79,
author = {Michael Sipser},
title = {Lower Bounds on the Size of Sweeping Automata},
booktitle = {Proceedings of the 11h Annual {ACM} Symposium on Theory of Computing,
April 30 - May 2, 1979, Atlanta, Georgia, {USA}},
pages = {360--364},
year = {1979},
crossref = {DBLP:conf/stoc/STOC11},
url = {https://doi.org/10.1145/800135.804429},
doi = {10.1145/800135.804429},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Sipser79.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LichtensteinS78,
author = {David Lichtenstein and
Michael Sipser},
title = {{GO} Is {PSPACE} Hard},
booktitle = {19th Annual Symposium on Foundations of Computer Science, Ann Arbor,
Michigan, USA, 16-18 October 1978},
pages = {48--54},
year = {1978},
crossref = {DBLP:conf/focs/FOCS19},
url = {https://doi.org/10.1109/SFCS.1978.17},
doi = {10.1109/SFCS.1978.17},
timestamp = {Tue, 08 Jul 2025 16:50:35 +0200},
biburl = {https://dblp.org/rec/conf/focs/LichtensteinS78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Sipser78,
author = {Michael Sipser},
title = {Halting Space-Bounded Computations},
booktitle = {19th Annual Symposium on Foundations of Computer Science, Ann Arbor,
Michigan, USA, 16-18 October 1978},
pages = {73--74},
year = {1978},
crossref = {DBLP:conf/focs/FOCS19},
url = {https://doi.org/10.1109/SFCS.1978.18},
doi = {10.1109/SFCS.1978.18},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Sipser78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SakodaS78,
author = {William J. Sakoda and
Michael Sipser},
title = {Nondeterminism and the Size of Two Way Finite Automata},
booktitle = {Proceedings of the 10th Annual {ACM} Symposium on Theory of Computing,
May 1-3, 1978, San Diego, California, {USA}},
pages = {275--286},
year = {1978},
crossref = {DBLP:conf/stoc/STOC10},
url = {https://doi.org/10.1145/800133.804357},
doi = {10.1145/800133.804357},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SakodaS78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KatseffS77,
author = {Howard P. Katseff and
Michael Sipser},
title = {Several Results in Program Size Complexity},
booktitle = {18th Annual Symposium on Foundations of Computer Science, Providence,
Rhode Island, USA, 31 October - 1 November 1977},
pages = {82--89},
year = {1977},
crossref = {DBLP:conf/focs/FOCS18},
url = {https://doi.org/10.1109/SFCS.1977.28},
doi = {10.1109/SFCS.1977.28},
timestamp = {Tue, 08 Jul 2025 16:50:50 +0200},
biburl = {https://dblp.org/rec/conf/focs/KatseffS77.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/1997,
editor = {Frank Thomson Leighton and
Peter W. Shor},
title = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory
of Computing, El Paso, Texas, USA, May 4-6, 1997},
publisher = {{ACM}},
year = {1997},
isbn = {0-89791-888-6},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/1997.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/colt/1994,
editor = {Manfred K. Warmuth},
title = {Proceedings of the Seventh Annual {ACM} Conference on Computational
Learning Theory, {COLT} 1994, New Brunswick, NJ, USA, July 12-15,
1994},
publisher = {{ACM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=180139},
isbn = {0-89791-655-7},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/colt/1994.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS35,
title = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
New Mexico, USA, November 20-22, 1994},
publisher = {{IEEE} Computer Society},
year = {1994},
url = {https://doi.org/10.1109/SFCS.1994},
doi = {10.1109/SFCS.1994},
isbn = {0-8186-6580-7},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS35.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/soda/1994,
editor = {Daniel Dominic Sleator},
title = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464},
isbn = {0-89871-329-3},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/soda/1994.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC24,
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
title = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
publisher = {{ACM}},
year = {1992},
isbn = {0-89791-511-9},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/1991,
title = {Proceedings of the Sixth Annual Structure in Complexity Theory Conference,
Chicago, Illinois, USA, June 30 - July 3, 1991},
publisher = {{IEEE} Computer Society},
year = {1991},
url = {https://ieeexplore.ieee.org/xpl/conhome/364/proceeding},
isbn = {0-8186-2255-5},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/coco/1991.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/1990,
title = {Proceedings: Fifth Annual Structure in Complexity Theory Conference,
Universitat Polit{\`{e}}cnica de Catalunya, Barcelona, Spain, July
8-11, 1990},
publisher = {{IEEE} Computer Society},
year = {1990},
url = {https://ieeexplore.ieee.org/xpl/conhome/476/proceeding},
isbn = {0-8186-2072-2},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/coco/1990.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/el/Leeuwen90,
editor = {Jan van Leeuwen},
title = {Handbook of Theoretical Computer Science, Volume {A:} Algorithms and
Complexity},
publisher = {Elsevier and {MIT} Press},
year = {1990},
crossref = {DBLP:books/el/Leeuwen90},
isbn = {0-444-88071-2},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/books/el/Leeuwen90.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 = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/coco/1988.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS29,
title = {29th Annual Symposium on Foundations of Computer Science, White Plains,
New York, USA, 24-26 October 1988},
publisher = {{IEEE} Computer Society},
year = {1988},
url = {https://doi.org/10.1109/SFCS.1988},
doi = {10.1109/SFCS.1988},
isbn = {0-8186-0877-3},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS29.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS28,
title = {28th Annual Symposium on Foundations of Computer Science, Los Angeles,
California, USA, 27-29 October 1987},
publisher = {{IEEE} Computer Society},
year = {1987},
url = {https://doi.org/10.1109/SFCS.1987},
doi = {10.1109/SFCS.1987},
isbn = {0-8186-0807-2},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS28.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/1986,
editor = {Alan L. Selman},
title = {Structure in Complexity Theory, Proceedings of the Conference hold
at the University of California, Berkeley, California, USA, June 2-5,
1986},
series = {Lecture Notes in Computer Science},
volume = {223},
publisher = {Springer},
year = {1986},
url = {https://doi.org/10.1007/3-540-16486-3},
doi = {10.1007/3-540-16486-3},
isbn = {3-540-16486-3},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/coco/1986.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC18,
editor = {Juris Hartmanis},
title = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA}},
publisher = {{ACM}},
year = {1986},
isbn = {0-89791-193-8},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC17,
editor = {Robert Sedgewick},
title = {Proceedings of the 17th Annual {ACM} Symposium on Theory of Computing,
May 6-8, 1985, Providence, Rhode Island, {USA}},
publisher = {{ACM}},
year = {1985},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS25,
title = {25th Annual Symposium on Foundations of Computer Science, West Palm
Beach, Florida, USA, 24-26 October 1984},
publisher = {{IEEE} Computer Society},
year = {1984},
url = {https://doi.org/10.1109/SFCS.1984},
doi = {10.1109/SFCS.1984},
isbn = {0-8186-0591-X},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS25.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/mfcs/1984,
editor = {Michal Chytil and
V{\'{a}}clav Koubek},
title = {Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia,
September 3-7, 1984, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {176},
publisher = {Springer},
year = {1984},
url = {https://doi.org/10.1007/BFb0030285},
doi = {10.1007/BFB0030285},
isbn = {3-540-13372-0},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/mfcs/1984.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC15,
editor = {David S. Johnson and
Ronald Fagin and
Michael L. Fredman and
David Harel and
Richard M. Karp and
Nancy A. Lynch and
Christos H. Papadimitriou and
Ronald L. Rivest and
Walter L. Ruzzo and
Joel I. Seiferas},
title = {Proceedings of the 15th Annual {ACM} Symposium on Theory of Computing,
25-27 April, 1983, Boston, Massachusetts, {USA}},
publisher = {{ACM}},
year = {1983},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/icalp/1982,
editor = {Mogens Nielsen and
Erik Meineche Schmidt},
title = {Automata, Languages and Programming, 9th Colloquium, Aarhus, Denmark,
July 12-16, 1982, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {140},
publisher = {Springer},
year = {1982},
url = {https://doi.org/10.1007/BFb0012751},
doi = {10.1007/BFB0012751},
isbn = {3-540-11576-5},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/icalp/1982.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC14,
editor = {Harry R. Lewis and
Barbara B. Simons and
Walter A. Burkhard and
Lawrence H. Landweber},
title = {Proceedings of the 14th Annual {ACM} Symposium on Theory of Computing,
May 5-7, 1982, San Francisco, California, {USA}},
publisher = {{ACM}},
year = {1982},
url = {https://doi.org/10.1145/800070},
doi = {10.1145/800070},
isbn = {0-89791-067-2},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS22,
title = {22nd Annual Symposium on Foundations of Computer Science, Nashville,
Tennessee, USA, 28-30 October 1981},
publisher = {{IEEE} Computer Society},
year = {1981},
url = {https://doi.org/10.1109/SFCS.1981},
doi = {10.1109/SFCS.1981},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC11,
editor = {Michael J. Fischer and
Richard A. DeMillo and
Nancy A. Lynch and
Walter A. Burkhard and
Alfred V. Aho},
title = {Proceedings of the 11h Annual {ACM} Symposium on Theory of Computing,
April 30 - May 2, 1979, Atlanta, Georgia, {USA}},
publisher = {{ACM}},
year = {1979},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS19,
title = {19th Annual Symposium on Foundations of Computer Science, Ann Arbor,
Michigan, USA, 16-18 October 1978},
publisher = {{IEEE} Computer Society},
year = {1978},
url = {https://doi.org/10.1109/SFCS.1978},
doi = {10.1109/SFCS.1978},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/STOC10,
editor = {Richard J. Lipton and
Walter A. Burkhard and
Walter J. Savitch and
Emily P. Friedman and
Alfred V. Aho},
title = {Proceedings of the 10th Annual {ACM} Symposium on Theory of Computing,
May 1-3, 1978, San Diego, California, {USA}},
publisher = {{ACM}},
year = {1978},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/focs/FOCS18,
title = {18th Annual Symposium on Foundations of Computer Science, Providence,
Rhode Island, USA, 31 October - 1 November 1977},
publisher = {{IEEE} Computer Society},
year = {1977},
url = {https://doi.org/10.1109/SFCS.1977},
doi = {10.1109/SFCS.1977},
timestamp = {Sun, 16 Nov 2025 12:41:26 +0100},
biburl = {https://dblp.org/rec/conf/focs/FOCS18.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.
last updated on 2025-10-28 23:14 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: