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},
editor = {Frank Thomson Leighton and
Peter W. Shor},
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},
publisher = {{ACM}},
year = {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},
editor = {Manfred K. Warmuth},
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},
publisher = {{ACM}},
year = {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},
publisher = {{IEEE} Computer Society},
year = {1994},
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},
editor = {Daniel Dominic Sleator},
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},
publisher = {{ACM/SIAM}},
year = {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},
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
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},
publisher = {{ACM}},
year = {1992},
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},
publisher = {{IEEE} Computer Society},
year = {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},
publisher = {{IEEE} Computer Society},
year = {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},
editor = {Jan van Leeuwen},
title = {The Complexity of Finite Functions},
booktitle = {Handbook of Theoretical Computer Science, Volume {A:} Algorithms and
Complexity},
pages = {757--804},
publisher = {Elsevier and {MIT} Press},
year = {1990},
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},
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/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},
publisher = {{IEEE} Computer Society},
year = {1988},
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},
publisher = {{IEEE} Computer Society},
year = {1987},
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},
editor = {Alan L. Selman},
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},
series = {Lecture Notes in Computer Science},
volume = {223},
pages = {325--329},
publisher = {Springer},
year = {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},
editor = {Juris Hartmanis},
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},
publisher = {{ACM}},
year = {1986},
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},
editor = {Robert Sedgewick},
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},
publisher = {{ACM}},
year = {1985},
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},
publisher = {{IEEE} Computer Society},
year = {1984},
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},
editor = {Michal Chytil and
V{\'{a}}clav Koubek},
title = {A Topological View of Some Problems in Complexity Theory},
booktitle = {Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia,
September 3-7, 1984, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {176},
pages = {567--572},
publisher = {Springer},
year = {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},
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 = {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},
publisher = {{ACM}},
year = {1983},
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},
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 = {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},
publisher = {{ACM}},
year = {1983},
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},
editor = {Mogens Nielsen and
Erik Meineche Schmidt},
title = {On Relativization and the Existence of Complete Sets},
booktitle = {Automata, Languages and Programming, 9th Colloquium, Aarhus, Denmark,
July 12-16, 1982, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {140},
pages = {523--531},
publisher = {Springer},
year = {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},
editor = {Harry R. Lewis and
Barbara B. Simons and
Walter A. Burkhard and
Lawrence H. Landweber},
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},
publisher = {{ACM}},
year = {1982},
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},
publisher = {{IEEE} Computer Society},
year = {1981},
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},
publisher = {{IEEE} Computer Society},
year = {1981},
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},
editor = {Michael J. Fischer and
Richard A. DeMillo and
Nancy A. Lynch and
Walter A. Burkhard and
Alfred V. Aho},
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},
publisher = {{ACM}},
year = {1979},
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},
publisher = {{IEEE} Computer Society},
year = {1978},
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},
publisher = {{IEEE} Computer Society},
year = {1978},
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},
editor = {Richard J. Lipton and
Walter A. Burkhard and
Walter J. Savitch and
Emily P. Friedman and
Alfred V. Aho},
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},
publisher = {{ACM}},
year = {1978},
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},
publisher = {{IEEE} Computer Society},
year = {1977},
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}
}
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: