introtcs.bib

@Book{hopcroft,
 author = {Hopcroft, John and Motwani, Rajeev and Ullman, Jeffrey},
 title = {Introduction to automata theory, languages, and computation},
 publisher = {Pearson Education},
 year = {2014},
 address = {Harlow, Essex},
 isbn = {1292039051}
 }

 @Book{kozen1997automata,
 author = {Kozen, Dexter},
 title = {Automata and computability},
 publisher = {Springer},
 year = {1997},
 address = {New York},
 isbn = {978-3-642-85706-5}
 }

@book{SipserBook,
  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 19:59:45 +0200},
  biburl    = {https://dblp.org/rec/bib/books/daglib/0086373},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@book{HopcroftUllman79,
  author    = {John E. Hopcroft and
               Jeffrey D. Ullman},
  title     = {Introduction to Automata Theory, Languages and Computation},
  publisher = {Addison-Wesley},
  year      = {1979},
  isbn      = {0-201-02988-X},
  timestamp = {Thu, 03 Jan 2002 11:51:07 +0100},
  biburl    = {https://dblp.org/rec/bib/books/aw/HopcroftU79},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@book{Boole1854,
  title={An investigation of the laws of thought: on which are founded the mathematical theories of logic and probabilities},
  author={Boole, George},
  year={1854},
  publisher={Dover Publications}
}


@book{DeMorgan1847,
  title={Formal logic: or, the calculus of inference, necessary and probable},
  author={De Morgan, Augustus},
  year={1847},
  publisher={Taylor and Walton}
}


@book{Boole1847mathematical,
  title={The mathematical analysis of logic},
  author={Boole, George},
  year={1847},
  publisher={Philosophical Library}
}

@article{Turing37,
  title={On computable numbers, with an application to the Entscheidungsproblem},
  author={Turing, Alan M},
  journal={Proceedings of the London mathematical society},
  volume={2},
  number={1},
  pages={230--265},
  year={1937}
}


@article{McCullochPitts43,
  title={A logical calculus of the ideas immanent in nervous activity},
  author={McCulloch, Warren S and Pitts, Walter},
  journal={The bulletin of mathematical biophysics},
  volume={5},
  number={4},
  pages={115--133},
  year={1943},
  publisher={Springer}
}


@article{RabinScott59,
  title={Finite automata and their decision problems},
  author={Rabin, Michael O and Scott, Dana},
  journal={IBM journal of research and development},
  volume={3},
  number={2},
  pages={114--125},
  year={1959},
  publisher={IBM}
}


@article{Chomsky56,
  title={Three models for the description of language},
  author={Chomsky, Noam},
  journal={IRE Transactions on information theory},
  volume={2},
  number={3},
  pages={113--124},
  year={1956},
  publisher={IEEE}
}

@article{Karatsuba95,
  title={The complexity of computations},
  author={Karatsuba, ANATOLII ALEXEEVICH},
  journal={Proceedings of the Steklov Institute of Mathematics-Interperiodica Translation},
  volume={211},
  pages={169--183},
  year={1995},
  publisher={Providence, RI: American Mathematical Society}
}


@inproceedings{Toom63,
  title={The complexity of a scheme of functional elements realizing the multiplication of integers},
  author={Toom, Andrei L},
  booktitle={Soviet Mathematics Doklady},
  volume={3},
  number={4},
  pages={714--716},
  year={1963}
}


@article{Cook66,
  title={On the minimum computation time for multiplication},
  author={Cook, SA},
  journal={Doctoral dissertation, Harvard University Department of Mathematics, Cambridge, Mass.},
  volume={1},
  year={1966}
}


@article{SchonhageStrassen71,
  title={Schnelle multiplikation grosser zahlen},
  author={Sch{\"o}nhage, Arnold and Strassen, Volker},
  journal={Computing},
  volume={7},
  number={3-4},
  pages={281--292},
  year={1971},
  publisher={Springer}
}

@inproceedings{Furer07,
  author    = {Martin F\"{u}rer},
  title     = {Faster integer multiplication},
  booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
               San Diego, California, USA, June 11-13, 2007},
  pages     = {57--66},
  year      = {2007},
}


@article{Strassen69,
  title={Gaussian elimination is not optimal},
  author={Strassen, Volker},
  journal={Numerische mathematik},
  volume={13},
  number={4},
  pages={354--356},
  year={1969},
  publisher={Springer}
}


@book{CLRS,
  author    = {Thomas H. Cormen and
               Charles E. Leiserson and
               Ronald L. Rivest and
               Clifford Stein},
  title     = {Introduction to Algorithms, 3rd Edition},
  publisher = {{MIT} Press},
  year      = {2009},
  url       = {http://mitpress.mit.edu/books/introduction-algorithms},
  isbn      = {978-0-262-03384-8},
  timestamp = {Fri, 12 May 2017 13:30:20 +0200},
  biburl    = {https://dblp.org/rec/bib/books/daglib/0023376},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


@book{KleinbergTardos06,
  author    = {Jon M. Kleinberg and
               {\'{E}}va Tardos},
  title     = {Algorithm design},
  publisher = {Addison-Wesley},
  year      = {2006},
  isbn      = {978-0-321-37291-8},
  timestamp = {Wed, 23 Mar 2011 16:58:37 +0100},
  biburl    = {https://dblp.org/rec/bib/books/daglib/0015106},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@book{DasguptaPV08,
  author    = {Sanjoy Dasgupta and
               Christos H. Papadimitriou and
               Umesh V. Vazirani},
  title     = {Algorithms},
  publisher = {McGraw-Hill},
  year      = {2008},
  isbn      = {978-0-07-352340-8},
  timestamp = {Wed, 09 Feb 2011 13:20:29 +0100},
  biburl    = {https://dblp.org/rec/bib/books/daglib/0017733},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


@book{Blaser13,
 author = {Bl{\"a}ser, Markus},
 title = {Fast Matrix Multiplication},
 year = {2013},
 pages = {1--60},
 doi = {10.4086/toc.gs.2013.005},
 publisher = {Theory of Computing Library},
 number = {5},
 series = {Graduate Surveys},
 URL = {http://www.theoryofcomputing.org/library.html},
}


@Book{LewisZax19,
author = {Lewis, Harry and Zax, Rachel},
title =  {Essential Discrete Mathematics for Computer Science},
publisher = {Princeton University Press},
year = {2019},
isbn = {9780691190617}
}

@Book{Livio05,
 author = {Livio, Mario},
 title = {The equation that couldn't be solved : how mathematical genius discovered the language of symmetry},
 publisher = {Simon \& Schuster},
 year = {2005},
 address = {New York},
 isbn = {0743258207}
 }


@article{Cooley87FFTdiscovery,
   title={The re-discovery of the fast Fourier transform algorithm},
   author={Cooley, James W},
   journal={Microchimica Acta},
   volume={93},
   number={1-6},
   pages={33--45},
   year={1987},
   publisher={Springer}
 }


@article{heideman1985gauss,
   title={Gauss and the history of the fast Fourier transform},
   author={Heideman, Michael T and Johnson, Don H and Burrus, C Sidney},
   journal={Archive for history of exact sciences},
   volume={34},
   number={3},
   pages={265--277},
   year={1985},
   publisher={Springer}
 }


@article{Werbos74,
   title={Beyond regression: New tools for prediction and analysis in the behavioral sciences. Ph. D. thesis, Harvard University, Cambridge, MA, 1974.},
   author={Werbos, PJ},
   year={1974}
 }


@techreport{pagerank99,
   title={The PageRank citation ranking: Bringing order to the web.},
   author={Page, Lawrence and Brin, Sergey and Motwani, Rajeev and Winograd, Terry},
   year={1999},
   institution={Stanford InfoLab}
 }

@article{Kleinber99,
   title={Authoritative sources in a hyperlinked environment},
   author={Kleinberg, Jon M},
   journal={Journal of the ACM (JACM)},
   volume={46},
   number={5},
   pages={604--632},
   year={1999},
   publisher={ACM}
 }

 @inproceedings{Akamai97,
   author    = {David R. Karger and
                Eric Lehman and
                Frank Thomson Leighton and
                Rina Panigrahy and
                Matthew S. Levine and
                Daniel Lewin},
   title     = {Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web},
   booktitle = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory                of Computing, El Paso, Texas, USA, May 4-6, 1997},
   pages     = {654--663},
   year      = {1997},
   url       = {https://doi.org/10.1145/258533.258660},
   doi       = {10.1145/258533.258660},
   timestamp = {Wed, 14 Nov 2018 10:51:37 +0100},
   biburl    = {https://dblp.org/rec/bib/conf/stoc/KargerLLPLL97},
   bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{compressedmri08,
  title={Compressed sensing MRI},
  author={Lustig, Michael and Donoho, David L and Santos, Juan M and Pauly, John M},
  journal={IEEE signal processing magazine},
  volume={25},
  number={2},
  pages={72--82},
  year={2008},
  publisher={IEEE}
}

@article{AgrawalKayalSaxena04,
  title={{PRIMES} is in {P}},
  author={Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin},
  journal={Annals of mathematics},
  pages={781--793},
  year={2004}
}

@article{CandesRombergTao06,
  title={Stable signal recovery from incomplete and inaccurate measurements},
  author={Candes, Emmanuel J and Romberg, Justin K and Tao, Terence},
  journal={Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences},
  volume={59},
  number={8},
  pages={1207--1223},
  year={2006},
}

@article{Donoho2006compressed,
  title={Compressed sensing},
  author={Donoho, David L},
  journal={IEEE Transactions on information theory},
  volume={52},
  number={4},
  pages={1289--1306},
  year={2006},
  publisher={IEEE}
}

@article{Ellenberg10wired,
  title={Fill in the blanks: Using math to turn lo-res datasets into hi-res samples},
  author={Ellenberg, Jordan},
  journal={Wired Magazine},
  volume={18},
  number={3},
  pages={501--509},
  year={2010}
}


@article{Hardy41,
  title={A Mathematician's Apology},
  author={Hardy, GH},
  year={1941}
}

@Book{LehmanLeightonMeyer,
title = {Mathematics for Computer Science},
author = {Lehman, Eric and Leighton, Thomson F. and Meyer, Albert R.},
year = {2018},
notes = {Lecture notes for MIT Course 6.042; latest version available from the course webpage.}
}

@Book{Rosen19discrete,
 author = {Rosen, Kenneth},
 title = {Discrete mathematics and its applications},
 publisher = {McGraw-Hill},
 year = {2019},
 address = {New York, NY},
 isbn = {125967651x}
}

@misc{Fleck,
 title = {Building Blocks for Theoretical Computer Science},
 author = {Margaret M. Fleck},
 year =  {2018},
 note = {Online book, available at \url{http://mfleck.cs.illinois.edu/building-blocks/}.}
}

@Book{Kun18,
 author = {Kun, Jeremy},
 title = {A programmer's introduction to mathematics},
 publisher = {CreateSpace Independent Publishing Platform},
 year = {2018},
 address = {Middletown, DE},
 isbn = {1727125452}
}

@misc{AspensDiscreteMath,
 author = {James Aspens},
 title = {Notes on Discrete Mathematics},
 year = {2018},
 note = {Online textbook for CS 202. Available on \url{http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf}.}
}

@Book{Solow14,
 author = {Solow, Daniel},
 title = {How to read and do proofs : an introduction to mathematical thought processes},
 publisher = {John Wiley \& Sons, Inc},
 year = {2014},
 address = {Hoboken, New Jersey},
 isbn = {9781118164020}
}


@article{CoverThomas06,
  title={Elements of information theory 2nd edition},
  author={Cover, Thomas M. and Thomas, Joy A.},
  journal={Willey-Interscience: NJ},
  year={2006},
 isbn = {0471241954}
 }


@book{MooreMertens11,
   title={The nature of computation},
   author={Moore, Cristopher and Mertens, Stephan},
   year={2011},
   publisher={Oxford University Press}
 }

 @book{Aaronson13democritus,
  title={Quantum computing since Democritus},
  author={Aaronson, Scott},
  year={2013},
  publisher={Cambridge University Press}
}


@book{Dauben90cantor,
  title={Georg Cantor: His mathematics and philosophy of the infinite},
  author={Dauben, Joseph Warren},
  year={1990},
  publisher={Princeton University Press}
}


@book{halmos1960naive,
  title={Naive set theory},
  author={Halmos, Paul R},
  year={1960},
  note ={Republished in 2017 by Courier Dover Publications.}
}


@article{Shannon1938,
  title={A symbolic analysis of relay and switching circuits},
  author={Shannon, Claude E},
  journal={Electrical Engineering},
  volume={57},
  number={12},
  pages={713--723},
  year={1938},
  publisher={IEEE}
}


@article{HopcroftUllman69,
  title={Formal languages and their relation to automata},
  author={Hopcroft, John E and Ullman, Jeffrey D},
  year={1969},
  publisher={Addison-Wesley Longman Publishing Co., Inc.}
}


@book{Savage1998models,
  title={Models of computation},
  author={Savage, John E},
  volume={136},
  year={1998},
  publisher={Addison-Wesley Reading, MA},
  note =  {Available electronically at \url{http://cs.brown.edu/people/jsavage/book/}.}
}


@article{Sheffer1913,
  title={A set of five independent postulates for Boolean algebras, with application to logical constants},
  author={Sheffer, Henry Maurice},
  journal={Transactions of the American mathematical society},
  volume={14},
  number={4},
  pages={481--488},
  year={1913},
  publisher={JSTOR}
}


@book{WhiteheadRussell1912,
  title={Principia mathematica},
  author={Whitehead, Alfred North and Russell, Bertrand},
  volume={2},
  year={1912},
  publisher={University Press}
}

@book{Peirce1976,
  title={The new elements of mathematics},
  author={Peirce, Charles Sanders and Eisele, Carolyn},
  volume={4},
  year={1976},
  publisher={Mouton The Hague},
  note = {Works of Charles Peirce, collected and edited by Carolyn Eisele.}
}



@article{Burks1978charles,
  title={Booke review: Charles S. Peirce, The new elements of mathematics},
  author={Burks, Arthur W},
  journal={Bulletin of the American Mathematical Society},
  volume={84},
  number={5},
  pages={913--918},
  year={1978},
  publisher={American Mathematical Society}
}


@book{Jukna12,
  title={Boolean function complexity: advances and frontiers},
  author={Jukna, Stasys},
  volume={27},
  year={2012},
  publisher={Springer Science \& Business Media}
}


@book{NisanShocken2005,
  title={The elements of computing systems: building a modern computer from first principles},
  author={Nisan, Noam and Schocken, Shimon},
  year={2005},
  publisher={MIT press}
}


@article{Lupanov1958,
  title={A circuit synthesis method},
  author={Lupanov, O},
  journal={Izv. Vuzov, Radiofizika},
  volume={1},
  number={1},
  pages={120--130},
  year={1958}
}


@inproceedings{Valiant1976,
  title={Universal circuits (preliminary report)},
  author={Valiant, Leslie G},
  booktitle={Proceedings of the eighth annual ACM symposium on Theory of computing},
  pages={196--203},
  year={1976},
  organization={ACM}
}

@article{lipmaa2016valiant,
  title={Valiant's Universal Circuit: Improvements, Implementation, and Applications.},
  author={Lipmaa, Helger and Mohassel, Payman and Sadeghian, Seyed Saeed},
  journal={IACR Cryptology ePrint Archive},
  volume={2016},
  pages={17},
  year={2016}
}

@inproceedings{Gunther2017,
  title={More efficient universal circuit constructions},
  author={G{\"u}nther, Daniel and Kiss, {\'A}gnes and Schneider, Thomas},
  booktitle={International Conference on the Theory and Application of Cryptology and Information Security},
  pages={443--470},
  year={2017},
  organization={Springer}
}


@book{wegener1987complexity,
  title={The complexity of Boolean functions},
  author={Wegener, Ingo},
  volume={1},
  year={1987},
  publisher={BG Teubner Stuttgart}
}


@phdthesis{Ernst2009phd,
  title={Optimal combinational multi-level logic synthesis},
  author={Ernst, Elizabeth Ann},
  year={2009},
  school={University of Michigan},
  note = {Available on \url{https://deepblue.lib.umich.edu/handle/2027.42/62373}.}
}


@Book{shetterly2016hidden,
 author = {Shetterly, Margot},
 title = {Hidden figures : the American dream and the untold story of the Black women mathematicians who helped win the space race},
 publisher = {William Morrow},
 year = {2016},
 address = {New York, NY},
 isbn = {9780062363602}
 }


@Book{sobel2017the,
  author = {Sobel, Dava},
  title = {The Glass Universe : How the Ladies of the Harvard Observatory Took the Measure of the Stars},
  publisher = {Penguin Books},
  year = {2017},
  address = {New York},
  isbn = {9780143111344}
  }


 @article{Wang1957,
    title={A variant to Turing's theory of computing machines},
    author={Wang, Hao},
    journal={Journal of the ACM (JACM)},
    volume={4},
    number={1},
    pages={63--92},
    year={1957},
    publisher={ACM}
  }


  @book{lupanov1984,
    title={Asymptotic complexity bounds for control circuits},
    author={Lupanov, Oleg B.},
    year={1984},
    publisher={MSU},
    note = {In Russian.}
  }


@Book{church1941,
 author = {Church, Alonzo},
 title = {The calculi of lambda-conversion},
 publisher = {Princeton University Press H. Milford, Oxford University Press},
 year = {1941},
 address = {Princeton London},
 isbn = {978-0-691-08394-0}
 }


 @Book{pierce2002types,
  author = {Pierce, Benjamin},
  title = {Types and programming languages},
  publisher = {MIT Press},
  year = {2002},
  address = {Cambridge, Mass},
  isbn = {0262162091}
  }


 @Book{barendregt1984,
   author = {Barendregt, H. P.},
   title = {The lambda calculus : its syntax and semantics},
   publisher = {North-Holland Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co},
   year = {1984},
   address = {Amsterdam New York New York, N.Y},
   isbn = {0444875085}
   }


@inproceedings{hagerup1998,
     title={Sorting and searching on the word RAM},
     author={Hagerup, Torben},
     booktitle={Annual Symposium on Theoretical Aspects of Computer Science},
     pages={366--398},
     year={1998},
     organization={Springer}
   }


@article{fredman1993,
     title={Surpassing the information theoretic bound with fusion trees},
     author={Fredman, Michael L and Willard, Dan E},
     journal={Journal of computer and system sciences},
     volume={47},
     number={3},
     pages={424--436},
     year={1993},
     publisher={Elsevier}
   }


@article{shamir1979,
     title={Factoring numbers in O (logn) arithmetic steps},
     author={Shamir, Adi},
     journal={Information Processing Letters},
     volume={8},
     number={1},
     pages={28--31},
     year={1979},
     publisher={Elsevier}
   }


@article{thompson1984reflections,
     title={Reflections on trusting trust},
     author={Thompson, Ken},
     journal={Communications of the ACM},
     volume={27},
     number={8},
     pages={761--763},
     year={1984},
     publisher={ACM}
   }



@Book{grabiner2005the,
    author = {Grabiner, Judith},
    title = {The origins of Cauchy's rigorous calculus},
    publisher = {Dover Publications},
    year = {2005},
    address = {Mineola, N.Y},
    isbn = {9780486438153}
    }

@article{grabiner1983gave,
      title={Who gave you the epsilon? Cauchy and the origins of rigorous calculus},
      author={Grabiner, Judith V},
      journal={The American Mathematical Monthly},
      volume={90},
      number={3},
      pages={185--194},
      year={1983},
      publisher={Taylor \& Francis}
}



@inbook{Lutzen2002,
place={Cambridge},
series={The Cambridge History of Science},
title={Between Rigor and Applications: Developments in the Concept of Function in Mathematical Analysis},
volume={5},
DOI={10.1017/CHOL9780521571999.026},
booktitle={The Cambridge History of Science},
publisher={Cambridge University Press},
author={Lützen, Jesper},
editor={Nye, Mary JoEditor},
year={2002},
pages={468–487},
collection={The Cambridge History of Science}
}


@article{Kleiner91,
 ISSN = {0025570X, 19300980},
 URL = {http://www.jstor.org/stable/2690647},
 author = {Israel Kleiner},
 journal = {Mathematics Magazine},
 number = {5},
 pages = {291--314},
 publisher = {Mathematical Association of America},
 title = {Rigor and Proof in Mathematics: A Historical Perspective},
 volume = {64},
 year = {1991}
}


@Book{cohen2008set,
 author = {Cohen, Paul},
 title = {Set theory and the continuum hypothesis},
 publisher = {Dover Publications},
 year = {2008},
 address = {Mineola, N.Y},
 isbn = {0486469212}
 }


@Book{hofstadter1999,
  author = {Hofstadter, Douglas},
  title = {Gödel, Escher, Bach : an eternal golden braid},
  publisher = {Basic Books},
  year = {1999},
  address = {New York},
  isbn = {0465026567}
  }


@Book{Holt2018,
   author = {Holt, Jim},
   title = {When Einstein walked with Gödel : excursions to the edge of thought},
   publisher = {Farrar, Straus and Giroux},
   year = {2018},
   address = {New York},
   isbn = {0374146705}
   }


@article{shelah2003logical,
     title={Logical dreams},
     author={Shelah, Saharon},
     journal={Bulletin of the American Mathematical Society},
     volume={40},
     number={2},
     pages={203--228},
     year={2003}
   }


@Book{singh1997fermat,
    author = {Singh, Simon},
    title = {Fermat's enigma : the quest to solve the world's greatest mathematical problem},
    publisher = {Walker},
    year = {1997},
    address = {New York},
    isbn = {0385493622}
    }


@article{rice1953classes,
      title={Classes of recursively enumerable sets and their decision problems},
      author={Rice, Henry Gordon},
      journal={Transactions of the American Mathematical Society},
      volume={74},
      number={2},
      pages={358--366},
      year={1953},
      publisher={JSTOR}
    }

@Book{stein1987ada,
     author = {Stein, Dorothy},
     title = {Ada : a life and a legacy},
     publisher = {MIT Press},
     year = {1987},
     address = {Cambridge, Mass},
     isbn = {0262691167}
     }

@article{holt2001ada,
       title={The Ada perplex: how Byron’s daughter came to be celebrated as a cybervisionary},
       author={Holt, Jim},
       journal={The New Yorker},
       volume={5},
       pages={88--93},
       year={2001}
     }

@book{collier2000charles,
       title={Charles Babbage: And the engines of perfection},
       author={Collier, Bruce and MacLachlan, James},
       year={2000},
       publisher={Oxford University Press}
     }

@Book{swade2002the,
      author = {Swade, Doron},
      title = {The difference engine : Charles Babbage and the quest to build the first computer},
      publisher = {Penguin Books},
      year = {2002},
      address = {New York},
      isbn = {0142001449}
      }


@article{vonNeumann45,
  title={First Draft of a Report on the EDVAC},
  author={von Neumann, John},
  year={1945},
  note ={Reprinted in the IEEE Annals of the History of Computing journal, 1993},
}


@unpublished{HarveyvdHoeven2019,
  TITLE = {Integer multiplication in time O(n log n)},
  AUTHOR = {Harvey, David and Van Der Hoeven, Joris},
  URL = {https://hal.archives-ouvertes.fr/hal-02070778},
  NOTE = {working paper or preprint},
  YEAR = {2019},
  MONTH = {3},
  PDF = {https://hal.archives-ouvertes.fr/hal-02070778/file/nlogn.pdf},
  HAL_ID = {hal-02070778},
  HAL_VERSION = {v1},
}


@article{schrijver2005history,
  title={On the history of combinatorial optimization (till 1960)},
  author={Schrijver, Alexander},
  journal={Handbooks in operations research and management science},
  volume={12},
  pages={1--68},
  year={2005},
  publisher={Elsevier}
}

@misc{TardosKleinberg,
  title={Algorithm Design},
  author={Tardos, Eva and Kleinberg, Jon},
  year={2006},
  publisher={Reading (MA): Addison-Wesley}
}

@book{dasgupta2008algorithms,
  title={Algorithms},
  author={Dasgupta, Sanjoy and Papadimitriou, Christos H and Vazirani, Umesh Virkumar},
  year={2008},
  publisher={McGraw-Hill Higher Education}
}


@article{maass1985combinatorial,
  title={Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines},
  author={Maass, Wolfgang},
  journal={Transactions of the American Mathematical Society},
  volume={292},
  number={2},
  pages={675--693},
  year={1985}
}

@article{gomes2008satisfiability,
  title={Satisfiability solvers},
  author={Gomes, Carla P and Kautz, Henry and Sabharwal, Ashish and Selman, Bart},
  journal={Foundations of Artificial Intelligence},
  volume={3},
  pages={89--134},
  year={2008},
  publisher={Elsevier}
}


@article{cohen1981holy,
  title={On holy wars and a plea for peace},
  author={Cohen, Danny},
  journal={Computer},
  volume={14},
  number={10},
  pages={48--54},
  year={1981},
  publisher={IEEE}
}

@article{cook1973time,
  title={Time bounded random access machines},
  author={Cook, Stephen A and Reckhow, Robert A},
  journal={Journal of Computer and System Sciences},
  volume={7},
  number={4},
  pages={354--375},
  year={1973},
  publisher={Elsevier}
}

@inproceedings{baiocchi2001three,
  title={Three small universal Turing machines},
  author={Baiocchi, Claudio},
  booktitle={International Conference on Machines, Computations, and Universality},
  pages={1--10},
  year={2001},
  organization={Springer}
}

@article{rogozhin1996small,
  title={Small universal Turing machines},
  author={Rogozhin, Yurii},
  journal={Theoretical Computer Science},
  volume={168},
  number={2},
  pages={215--240},
  year={1996},
  publisher={Elsevier}
}

@article{woods2009complexity,
  title={The complexity of small universal Turing machines: A survey},
  author={Woods, Damien and Neary, Turlough},
  journal={Theoretical Computer Science},
  volume={410},
  number={4-5},
  pages={443--450},
  year={2009},
  publisher={Elsevier}
}

@book{mermin2007quantum,
  title={Quantum computer science: an introduction},
  author={Mermin, N David},
  year={2007},
  publisher={Cambridge University Press}
}


@article{williams2009finding,
  title={Finding paths of length k in $O^*(2^k)$ time},
  author={Williams, Ryan},
  journal={Information Processing Letters},
  volume={109},
  number={6},
  pages={315--318},
  year={2009},
  publisher={Elsevier}
}

@article{bjorklund2014determinant,
  title={Determinant sums for undirected hamiltonicity},
  author={Bjorklund, Andreas},
  journal={SIAM Journal on Computing},
  volume={43},
  number={1},
  pages={280--299},
  year={2014},
  publisher={SIAM}
}


@article{buchfuhrer2011complexity,
  title={The complexity of Boolean formula minimization},
  author={Buchfuhrer, David and Umans, Christopher},
  journal={Journal of Computer and System Sciences},
  volume={77},
  number={1},
  pages={142--153},
  year={2011},
  publisher={Elsevier}
}

@incollection{aaronson2016p,
  title={P =? NP},
  author={Aaronson, Scott},
  booktitle={Open problems in mathematics},
  pages={1--122},
  year={2016},
  publisher={Springer},
  note = {Available on \url{https://www.scottaaronson.com/papers/pnp.pdf}}
}



@article{aaronson2005physicalreality,
  title={NP-complete problems and physical reality},
  author={Aaronson, Scott},
  journal={ACM Sigact News},
  volume={36},
  number={1},
  pages={30--52},
  year={2005},
  publisher={ACM},
  note = {Available on \url{https://arxiv.org/abs/quant-ph/0502072}}
}



@article{johnson2012brief,
  title={A brief history of NP-completeness, 1954--2012},
  author={Johnson, David S},
  journal={Documenta Mathematica},
  pages={359--376},
  year={2012}
}




@book{wigderson2017mathematics,
  title={Mathematics and Computation},
  author={Wigderson, Avi},
  year={2019},
  publisher = {Princeton University Press},
  note = {Draft available on \url{https://www.math.ias.edu/avi/book}}
}


@article{vadhan2012pseudorandomness,
  title={Pseudorandomness},
  author={Vadhan, Salil P and others},
  journal={Foundations and Trends{\textregistered} in Theoretical Computer Science},
  volume={7},
  number={1--3},
  pages={1--336},
  year={2012},
  publisher={Now Publishers, Inc.}
}


@book{motwani1995randomized,
  title={Randomized algorithms},
  author={Motwani, Rajeev and Raghavan, Prabhakar},
  year={1995},
  publisher={Cambridge university press}
}



@book{mitzenmacher2017probability,
  title={Probability and computing: randomization and probabilistic techniques in algorithms and data analysis},
  author={Mitzenmacher, Michael and Upfal, Eli},
  year={2017},
  publisher={Cambridge university press}
}

@article{woods2009complexity,
  title={The complexity of small universal Turing machines: A survey},
  author={Woods, Damien and Neary, Turlough},
  journal={Theoretical Computer Science},
  volume={410},
  number={4-5},
  pages={443--450},
  year={2009},
  publisher={Elsevier}
}

@article{aaronson20beaver,
title = {The Busy Beaver Frontier},
author = {Scott Aaronson},
year = {2020},
note = {Available on \url{https://www.scottaaronson.com/papers/bb.pdf}},
journal = {{SIGACT} News}
}


@inproceedings{Shor94,
  author    = {Peter W. Shor},
  title     = {Algorithms for Quantum Computation: Discrete Logarithms and Factoring},
  booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
               New Mexico, USA, 20-22 November 1994},
  pages     = {124--134},
  publisher = {{IEEE} Computer Society},
  year      = {1994},
  url       = {https://doi.org/10.1109/SFCS.1994.365700},
  doi       = {10.1109/SFCS.1994.365700},
  timestamp = {Wed, 16 Oct 2019 14:14:54 +0200},
  biburl    = {https://dblp.org/rec/conf/focs/Shor94.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}