Stop the war!
Остановите войну!
for scientists:
default search action
BibTeX records: Miklós Ajtai
@inproceedings{DBLP:conf/pods/AjtaiBJSSWZ22, author = {Mikl{\'{o}}s Ajtai and Vladimir Braverman and T. S. Jayram and Sandeep Silwal and Alec Sun and David P. Woodruff and Samson Zhou}, editor = {Leonid Libkin and Pablo Barcel{\'{o}}}, title = {The White-Box Adversarial Data Stream Model}, booktitle = {{PODS} '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022}, pages = {15--27}, publisher = {{ACM}}, year = {2022}, url = {https://doi.org/10.1145/3517804.3526228}, doi = {10.1145/3517804.3526228}, timestamp = {Wed, 15 Jun 2022 08:52:54 +0200}, biburl = {https://dblp.org/rec/conf/pods/AjtaiBJSSWZ22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2204-09136, author = {Mikl{\'{o}}s Ajtai and Vladimir Braverman and T. S. Jayram and Sandeep Silwal and Alec Sun and David P. Woodruff and Samson Zhou}, title = {The White-Box Adversarial Data Stream Model}, journal = {CoRR}, volume = {abs/2204.09136}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2204.09136}, doi = {10.48550/ARXIV.2204.09136}, eprinttype = {arXiv}, eprint = {2204.09136}, timestamp = {Mon, 25 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2204-09136.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/talg/AjtaiFHN16, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, title = {Sorting and Selection with Imprecise Comparisons}, journal = {{ACM} Trans. Algorithms}, volume = {12}, number = {2}, pages = {19:1--19:19}, year = {2016}, url = {https://doi.org/10.1145/2701427}, doi = {10.1145/2701427}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/talg/AjtaiFHN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/AjtaiFHN15, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, title = {Sorting and Selection with Imprecise Comparisons}, journal = {CoRR}, volume = {abs/1501.02911}, year = {2015}, url = {http://arxiv.org/abs/1501.02911}, eprinttype = {arXiv}, eprint = {1501.02911}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/AjtaiFHN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai13, author = {Mikl{\'{o}}s Ajtai}, editor = {Dan Boneh and Tim Roughgarden and Joan Feigenbaum}, title = {Lower bounds for RAMs and quantifier elimination}, booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}, pages = {803--812}, publisher = {{ACM}}, year = {2013}, url = {https://doi.org/10.1145/2488608.2488710}, doi = {10.1145/2488608.2488710}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/Ajtai13, author = {Mikl{\'{o}}s Ajtai}, title = {Lower Bounds for RAMs and Quantifier Elimination}, journal = {CoRR}, volume = {abs/1306.0153}, year = {2013}, url = {http://arxiv.org/abs/1306.0153}, eprinttype = {arXiv}, eprint = {1306.0153}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/Ajtai13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/Ajtai13, author = {Mikl{\'{o}}s Ajtai}, title = {Lower Bounds for RAMs and Quantifier Elimination}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR13-083}}, year = {2013}, url = {https://eccc.weizmann.ac.il/report/2013/083}, eprinttype = {ECCC}, eprint = {TR13-083}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/Ajtai13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai12, author = {Mikl{\'{o}}s Ajtai}, editor = {Howard J. Karloff and Toniann Pitassi}, title = {Determinism versus nondeterminism with arithmetic tests and computation: extended abstract}, booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference, {STOC} 2012, New York, NY, USA, May 19 - 22, 2012}, pages = {249--268}, publisher = {{ACM}}, year = {2012}, url = {https://doi.org/10.1145/2213977.2214001}, doi = {10.1145/2213977.2214001}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai11, author = {Mikl{\'{o}}s Ajtai}, editor = {Lance Fortnow and Salil P. Vadhan}, title = {Secure computation with information leaking to an adversary}, booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC} 2011, San Jose, CA, USA, 6-8 June 2011}, pages = {715--724}, publisher = {{ACM}}, year = {2011}, url = {https://doi.org/10.1145/1993636.1993731}, doi = {10.1145/1993636.1993731}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/Ajtai11, author = {Mikl{\'{o}}s Ajtai}, title = {Secure Computation with Information Leaking to an Adversary}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR11-082}}, year = {2011}, url = {https://eccc.weizmann.ac.il/report/2011/082}, eprinttype = {ECCC}, eprint = {TR11-082}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/Ajtai11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/Ajtai11a, author = {Mikl{\'{o}}s Ajtai}, title = {Determinism Versus Nondeterminism with Arithmetic Tests and Computation}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR11-102}}, year = {2011}, url = {https://eccc.weizmann.ac.il/report/2011/102}, eprinttype = {ECCC}, eprint = {TR11-102}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/Ajtai11a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai10, author = {Mikl{\'{o}}s Ajtai}, editor = {Leonard J. Schulman}, title = {Oblivious RAMs without cryptogrpahic assumptions}, booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC} 2010, Cambridge, Massachusetts, USA, 5-8 June 2010}, pages = {181--190}, publisher = {{ACM}}, year = {2010}, url = {https://doi.org/10.1145/1806689.1806716}, doi = {10.1145/1806689.1806716}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/Ajtai10, author = {Mikl{\'{o}}s Ajtai}, title = {Oblivious RAMs without Cryptographic Assumptions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR10-028}}, year = {2010}, url = {https://eccc.weizmann.ac.il/report/2010/028}, eprinttype = {ECCC}, eprint = {TR10-028}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/Ajtai10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/AjtaiFHN09, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, editor = {Susanne Albers and Alberto Marchetti{-}Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas}, title = {Sorting and Selection with Imprecise Comparisons}, booktitle = {Automata, Languages and Programming, 36th International Colloquium, {ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}}, series = {Lecture Notes in Computer Science}, volume = {5555}, pages = {37--48}, publisher = {Springer}, year = {2009}, url = {https://doi.org/10.1007/978-3-642-02927-1\_5}, doi = {10.1007/978-3-642-02927-1\_5}, timestamp = {Tue, 14 May 2019 10:00:44 +0200}, biburl = {https://dblp.org/rec/conf/icalp/AjtaiFHN09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/cjtcs/Ajtai08, author = {Mikl{\'{o}}s Ajtai}, title = {Representing Hard Lattices with O(nlog n) Bits}, journal = {Chic. J. Theor. Comput. Sci.}, volume = {2008}, year = {2008}, url = {http://cjtcs.cs.uchicago.edu/articles/2008/2/contents.html}, timestamp = {Thu, 11 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/cjtcs/Ajtai08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toc/Ajtai08, author = {Mikl{\'{o}}s Ajtai}, title = {Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem}, journal = {Theory Comput.}, volume = {4}, number = {1}, pages = {21--51}, year = {2008}, url = {https://doi.org/10.4086/toc.2008.v004a002}, doi = {10.4086/TOC.2008.V004A002}, timestamp = {Sun, 21 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toc/Ajtai08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/tamc/Ajtai07, author = {Mikl{\'{o}}s Ajtai}, editor = {Jin{-}yi Cai and S. Barry Cooper and Hong Zhu}, title = {Generalizations of the Compactness Theorem and G{\"{o}}del's Completeness Theorem for Nonstandard Finite Structures}, booktitle = {Theory and Applications of Models of Computation, 4th International Conference, {TAMC} 2007, Shanghai, China, May 22-25, 2007, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {4484}, pages = {13--33}, publisher = {Springer}, year = {2007}, url = {https://doi.org/10.1007/978-3-540-72504-6\_2}, doi = {10.1007/978-3-540-72504-6\_2}, timestamp = {Mon, 04 May 2020 13:17:48 +0200}, biburl = {https://dblp.org/rec/conf/tamc/Ajtai07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/AjtaiD07, author = {Mikl{\'{o}}s Ajtai and Cynthia Dwork}, title = {The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR07-097}}, year = {2007}, url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-097/index.html}, eprinttype = {ECCC}, eprint = {TR07-097}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/AjtaiD07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/latin/AjtaiDS06, author = {Mikl{\'{o}}s Ajtai and Cynthia Dwork and Larry J. Stockmeyer}, editor = {Jos{\'{e}} R. Correa and Alejandro Hevia and Marcos A. Kiwi}, title = {An Architecture for Provably Secure Computation}, booktitle = {{LATIN} 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {3887}, pages = {56--67}, publisher = {Springer}, year = {2006}, url = {https://doi.org/10.1007/11682462\_10}, doi = {10.1007/11682462\_10}, timestamp = {Tue, 14 May 2019 10:00:53 +0200}, biburl = {https://dblp.org/rec/conf/latin/AjtaiDS06.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toc/Ajtai05, author = {Mikl{\'{o}}s Ajtai}, title = {A Non-linear Time Lower Bound for Boolean Branching Programs}, journal = {Theory Comput.}, volume = {1}, number = {1}, pages = {149--176}, year = {2005}, url = {https://doi.org/10.4086/toc.2005.v001a008}, doi = {10.4086/TOC.2005.V001A008}, timestamp = {Sun, 21 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toc/Ajtai05.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai05, author = {Mikl{\'{o}}s Ajtai}, editor = {Harold N. Gabow and Ronald Fagin}, title = {Representing hard lattices with O(n log n) bits}, booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}, pages = {94--103}, publisher = {{ACM}}, year = {2005}, url = {https://doi.org/10.1145/1060590.1060604}, doi = {10.1145/1060590.1060604}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai05.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai04, author = {Mikl{\'{o}}s Ajtai}, editor = {L{\'{a}}szl{\'{o}} Babai}, title = {A conjecture about polynomial time computable lattice-lattice functions}, booktitle = {Proceedings of the 36th Annual {ACM} Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004}, pages = {486--493}, publisher = {{ACM}}, year = {2004}, url = {https://doi.org/10.1145/1007352.1007426}, doi = {10.1145/1007352.1007426}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai04.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai03, author = {Mikl{\'{o}}s Ajtai}, editor = {Lawrence L. Larmore and Michel X. Goemans}, title = {The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice}, booktitle = {Proceedings of the 35th Annual {ACM} Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, {USA}}, pages = {396--406}, publisher = {{ACM}}, year = {2003}, url = {https://doi.org/10.1145/780542.780602}, doi = {10.1145/780542.780602}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai03.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jacm/AjtaiBFLS02, author = {Mikl{\'{o}}s Ajtai and Randal C. Burns and Ronald Fagin and Darrell D. E. Long and Larry J. Stockmeyer}, title = {Compactly encoding unstructured inputs with differential compression}, journal = {J. {ACM}}, volume = {49}, number = {3}, pages = {318--367}, year = {2002}, url = {https://doi.org/10.1145/567112.567116}, doi = {10.1145/567112.567116}, timestamp = {Mon, 26 Oct 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jacm/AjtaiBFLS02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jcss/Ajtai02, author = {Mikl{\'{o}}s Ajtai}, title = {Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions}, journal = {J. Comput. Syst. Sci.}, volume = {65}, number = {1}, pages = {2--37}, year = {2002}, url = {https://doi.org/10.1006/jcss.2002.1821}, doi = {10.1006/JCSS.2002.1821}, timestamp = {Tue, 16 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jcss/Ajtai02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/coco/AjtaiKS02, author = {Mikl{\'{o}}s Ajtai and Ravi Kumar and D. Sivakumar}, title = {Sampling Short Lattice Vectors and the Closest Lattice Vector Problem}, booktitle = {Proceedings of the 17th Annual {IEEE} Conference on Computational Complexity, Montr{\'{e}}al, Qu{\'{e}}bec, Canada, May 21-24, 2002}, pages = {53--57}, publisher = {{IEEE} Computer Society}, year = {2002}, url = {https://doi.org/10.1109/CCC.2002.1004339}, doi = {10.1109/CCC.2002.1004339}, timestamp = {Fri, 24 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/coco/AjtaiKS02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Ajtai02, author = {Mikl{\'{o}}s Ajtai}, title = {Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties}, booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings}, pages = {733--742}, publisher = {{IEEE} Computer Society}, year = {2002}, url = {https://doi.org/10.1109/SFCS.2002.1181998}, doi = {10.1109/SFCS.2002.1181998}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Ajtai02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiJKS02, author = {Mikl{\'{o}}s Ajtai and T. S. Jayram and Ravi Kumar and D. Sivakumar}, editor = {John H. Reif}, title = {Approximate counting of inversions in a data stream}, booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing, May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada}, pages = {370--379}, publisher = {{ACM}}, year = {2002}, url = {https://doi.org/10.1145/509907.509964}, doi = {10.1145/509907.509964}, timestamp = {Mon, 08 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiJKS02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai02, author = {Mikl{\'{o}}s Ajtai}, editor = {John H. Reif}, title = {The invasiveness of off-line memory checking}, booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing, May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada}, pages = {504--513}, publisher = {{ACM}}, year = {2002}, url = {https://doi.org/10.1145/509907.509981}, doi = {10.1145/509907.509981}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai02.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR02-061, author = {Mikl{\'{o}}s Ajtai}, title = {A conjectured 0-1 law about the polynomial time computable properties of random lattices, {I}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR02-061}}, year = {2002}, url = {https://eccc.weizmann.ac.il/eccc-reports/2002/TR02-061/index.html}, eprinttype = {ECCC}, eprint = {TR02-061}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR02-061.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/siamdm/AjtaiMW01, author = {Mikl{\'{o}}s Ajtai and Nimrod Megiddo and Orli Waarts}, title = {Improved Algorithms and Analysis for Secretary Problems and Generalizations}, journal = {{SIAM} J. Discret. Math.}, volume = {14}, number = {1}, pages = {1--27}, year = {2001}, url = {https://doi.org/10.1137/S0895480195290017}, doi = {10.1137/S0895480195290017}, timestamp = {Sat, 25 Apr 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/siamdm/AjtaiMW01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/calc/AjtaiKS01, author = {Mikl{\'{o}}s Ajtai and Ravi Kumar and D. Sivakumar}, editor = {Joseph H. Silverman}, title = {An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem}, booktitle = {Cryptography and Lattices, International Conference, CaLC 2001, Providence, RI, USA, March 29-30, 2001, Revised Papers}, series = {Lecture Notes in Computer Science}, volume = {2146}, pages = {1--3}, publisher = {Springer}, year = {2001}, url = {https://doi.org/10.1007/3-540-44670-2\_1}, doi = {10.1007/3-540-44670-2\_1}, timestamp = {Mon, 08 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/calc/AjtaiKS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiKS01, author = {Mikl{\'{o}}s Ajtai and Ravi Kumar and D. Sivakumar}, editor = {Jeffrey Scott Vitter and Paul G. Spirakis and Mihalis Yannakakis}, title = {A sieve algorithm for the shortest lattice vector problem}, booktitle = {Proceedings on 33rd Annual {ACM} Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece}, pages = {601--610}, publisher = {{ACM}}, year = {2001}, url = {https://doi.org/10.1145/380752.380857}, doi = {10.1145/380752.380857}, timestamp = {Mon, 08 Mar 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiKS01.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jcss/AjtaiFS00, author = {Mikl{\'{o}}s Ajtai and Ronald Fagin and Larry J. Stockmeyer}, title = {The Closure of Monadic {NP}}, journal = {J. Comput. Syst. Sci.}, volume = {60}, number = {3}, pages = {660--716}, year = {2000}, url = {https://doi.org/10.1006/jcss.1999.1691}, doi = {10.1006/JCSS.1999.1691}, timestamp = {Tue, 16 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jcss/AjtaiFS00.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Ajtai99, author = {Mikl{\'{o}}s Ajtai}, title = {A Non-linear Time Lower Bound for Boolean Branching Programs}, booktitle = {40th Annual Symposium on Foundations of Computer Science, {FOCS} '99, 17-18 October, 1999, New York, NY, {USA}}, pages = {60--70}, publisher = {{IEEE} Computer Society}, year = {1999}, url = {https://doi.org/10.1109/SFFCS.1999.814578}, doi = {10.1109/SFFCS.1999.814578}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Ajtai99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/Ajtai99, author = {Mikl{\'{o}}s Ajtai}, editor = {Jir{\'{\i}} Wiedermann and Peter van Emde Boas and Mogens Nielsen}, title = {Generating Hard Instances of the Short Basis Problem}, booktitle = {Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {1644}, pages = {1--9}, publisher = {Springer}, year = {1999}, url = {https://doi.org/10.1007/3-540-48523-6\_1}, doi = {10.1007/3-540-48523-6\_1}, timestamp = {Tue, 14 May 2019 10:00:44 +0200}, biburl = {https://dblp.org/rec/conf/icalp/Ajtai99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai99, author = {Mikl{\'{o}}s Ajtai}, editor = {Jeffrey Scott Vitter and Lawrence L. Larmore and Frank Thomson Leighton}, title = {Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract)}, booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, {USA}}, pages = {632--641}, publisher = {{ACM}}, year = {1999}, url = {https://doi.org/10.1145/301250.301424}, doi = {10.1145/301250.301424}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR99-026, author = {Mikl{\'{o}}s Ajtai}, title = {A Non-linear Time Lower Bound for Boolean Branching Programs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR99-026}}, year = {1999}, url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-026/index.html}, eprinttype = {ECCC}, eprint = {TR99-026}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-026.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jal/AjtaiANRSW98, author = {Mikl{\'{o}}s Ajtai and James Aspnes and Moni Naor and Yuval Rabani and Leonard J. Schulman and Orli Waarts}, title = {Fairness in Scheduling}, journal = {J. Algorithms}, volume = {29}, number = {2}, pages = {306--357}, year = {1998}, url = {https://doi.org/10.1006/jagm.1998.0953}, doi = {10.1006/JAGM.1998.0953}, timestamp = {Tue, 21 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jal/AjtaiANRSW98.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai98, author = {Mikl{\'{o}}s Ajtai}, editor = {Jeffrey Scott Vitter}, title = {The Shortest Vector Problem in \emph{L\({}_{\mbox{2}}\)} is \emph{NP}-hard for Randomized Reductions (Extended Abstract)}, booktitle = {Proceedings of the Thirtieth Annual {ACM} Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998}, pages = {10--19}, publisher = {{ACM}}, year = {1998}, url = {https://doi.org/10.1145/276698.276705}, doi = {10.1145/276698.276705}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai98.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiFS98, author = {Mikl{\'{o}}s Ajtai and Ronald Fagin and Larry J. Stockmeyer}, editor = {Jeffrey Scott Vitter}, title = {The Closure of Monadic {NP} (Extended Abstract)}, booktitle = {Proceedings of the Thirtieth Annual {ACM} Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998}, pages = {309--318}, publisher = {{ACM}}, year = {1998}, url = {https://doi.org/10.1145/276698.276771}, doi = {10.1145/276698.276771}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiFS98.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR98-077, author = {Mikl{\'{o}}s Ajtai}, title = {Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR98-077}}, year = {1998}, url = {https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-077/index.html}, eprinttype = {ECCC}, eprint = {TR98-077}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR98-077.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiD97, author = {Mikl{\'{o}}s Ajtai and Cynthia Dwork}, editor = {Frank Thomson Leighton and Peter W. Shor}, title = {A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence}, booktitle = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997}, pages = {284--293}, publisher = {{ACM}}, year = {1997}, url = {https://doi.org/10.1145/258533.258604}, doi = {10.1145/258533.258604}, timestamp = {Mon, 26 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiD97.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR97-047, author = {Mikl{\'{o}}s Ajtai}, title = {The Shortest Vector Problem in L\({}_{\mbox{2}}\) is NP-hard for Randomized Reductions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR97-047}}, year = {1997}, url = {https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-047/index.html}, eprinttype = {ECCC}, eprint = {TR97-047}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR97-047.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/siamcomp/AjtaiM96, author = {Mikl{\'{o}}s Ajtai and Nimrod Megiddo}, title = {A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions}, journal = {{SIAM} J. Comput.}, volume = {25}, number = {6}, pages = {1171--1195}, year = {1996}, url = {https://doi.org/10.1137/S0097539792234858}, doi = {10.1137/S0097539792234858}, timestamp = {Sat, 27 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/siamcomp/AjtaiM96.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Ajtai96, author = {Mikl{\'{o}}s Ajtai}, editor = {Gary L. Miller}, title = {Generating Hard Instances of Lattice Problems (Extended Abstract)}, booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996}, pages = {99--108}, publisher = {{ACM}}, year = {1996}, url = {https://doi.org/10.1145/237814.237838}, doi = {10.1145/237814.237838}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/Ajtai96.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR96-007, author = {Mikl{\'{o}}s Ajtai}, title = {Generating Hard Instances of Lattice Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR96-007}}, year = {1996}, url = {https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-007/index.html}, eprinttype = {ECCC}, eprint = {TR96-007}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR96-007.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR96-065, author = {Mikl{\'{o}}s Ajtai and Cynthia Dwork}, title = {A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR96-065}}, year = {1996}, url = {https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-065/index.html}, eprinttype = {ECCC}, eprint = {TR96-065}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR96-065.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiMW95, author = {Mikl{\'{o}}s Ajtai and Nimrod Megiddo and Orli Waarts}, title = {Improved Algorithms and Analysis for Secretary Problems and Generalizations}, booktitle = {36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995}, pages = {473--482}, publisher = {{IEEE} Computer Society}, year = {1995}, url = {https://doi.org/10.1109/SFCS.1995.492578}, doi = {10.1109/SFCS.1995.492578}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiMW95.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/AjtaiANRSW95, author = {Mikl{\'{o}}s Ajtai and James Aspnes and Moni Naor and Yuval Rabani and Leonard J. Schulman and Orli Waarts}, editor = {Kenneth L. Clarkson}, title = {Fairness in Scheduling}, booktitle = {Proceedings of the Sixth Annual {ACM-SIAM} Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California, {USA}}, pages = {477--485}, publisher = {{ACM/SIAM}}, year = {1995}, url = {http://dl.acm.org/citation.cfm?id=313651.313796}, timestamp = {Thu, 05 Jul 2018 07:29:25 +0200}, biburl = {https://dblp.org/rec/conf/soda/AjtaiANRSW95.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/Ajtai94, author = {Mikl{\'{o}}s Ajtai}, title = {Recursive Construction for 3-Regular Expanders}, journal = {Comb.}, volume = {14}, number = {4}, pages = {379--416}, year = {1994}, url = {https://doi.org/10.1007/BF01302963}, doi = {10.1007/BF01302963}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/Ajtai94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/Ajtai94a, author = {Mikl{\'{o}}s Ajtai}, title = {The Complexity of the Pigeonhole Principle}, journal = {Comb.}, volume = {14}, number = {4}, pages = {417--433}, year = {1994}, url = {https://doi.org/10.1007/BF01302964}, doi = {10.1007/BF01302964}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/Ajtai94a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jcss/AjtaiG94, author = {Mikl{\'{o}}s Ajtai and Yuri Gurevich}, title = {Datalog vs First-Order Logic}, journal = {J. Comput. Syst. Sci.}, volume = {49}, number = {3}, pages = {562--588}, year = {1994}, url = {https://doi.org/10.1016/S0022-0000(05)80071-6}, doi = {10.1016/S0022-0000(05)80071-6}, timestamp = {Tue, 16 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jcss/AjtaiG94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiADW94, author = {Mikl{\'{o}}s Ajtai and James Aspnes and Cynthia Dwork and Orli Waarts}, title = {A Theory of Competitive Analysis for Distributed Algorithms}, booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994}, pages = {401--411}, publisher = {{IEEE} Computer Society}, year = {1994}, url = {https://doi.org/10.1109/SFCS.1994.365676}, doi = {10.1109/SFCS.1994.365676}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiADW94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/podc/AjtaiADW94, author = {Mikl{\'{o}}s Ajtai and James Aspnes and Cynthia Dwork and Orli Waarts}, editor = {James H. Anderson and David Peleg and Elizabeth Borowsky}, title = {Competitiveness in Distributed Algorithms}, booktitle = {Proceedings of the Thirteenth Annual {ACM} Symposium on Principles of Distributed Computing, Los Angeles, California, USA, August 14-17, 1994}, pages = {398}, publisher = {{ACM}}, year = {1994}, url = {https://doi.org/10.1145/197917.198178}, doi = {10.1145/197917.198178}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/podc/AjtaiADW94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR94-014, author = {Mikl{\'{o}}s Ajtai}, title = {The Independence of the modulo p Counting Principles}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR94-014}}, year = {1994}, url = {https://eccc.weizmann.ac.il/eccc-reports/1994/TR94-014/index.html}, eprinttype = {ECCC}, eprint = {TR94-014}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR94-014.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR94-015, author = {Mikl{\'{o}}s Ajtai}, title = {Symmetric Systems of Linear Equations modulo p}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR94-015}}, year = {1994}, url = {https://eccc.weizmann.ac.il/eccc-reports/1994/TR94-015/index.html}, eprinttype = {ECCC}, eprint = {TR94-015}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR94-015.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiL93, author = {Mikl{\'{o}}s Ajtai and Nathan Linial}, title = {The influence of large coalitions}, journal = {Comb.}, volume = {13}, number = {2}, pages = {129--145}, year = {1993}, url = {https://doi.org/10.1007/BF01303199}, doi = {10.1007/BF01303199}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiL93.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiKS92, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {Halvers and Expanders}, booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}, pages = {686--692}, publisher = {{IEEE} Computer Society}, year = {1992}, url = {https://doi.org/10.1109/SFCS.1992.267782}, doi = {10.1109/SFCS.1992.267782}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiKS92.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiABCHNS92, author = {Mikl{\'{o}}s Ajtai and Noga Alon and Jehoshua Bruck and Robert Cypher and Ching{-}Tien Ho and Moni Naor and Endre Szemer{\'{e}}di}, title = {Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths}, booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}, pages = {693--702}, publisher = {{IEEE} Computer Society}, year = {1992}, url = {https://doi.org/10.1109/SFCS.1992.267781}, doi = {10.1109/SFCS.1992.267781}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiABCHNS92.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiM92, author = {Mikl{\'{o}}s Ajtai and Nimrod Megiddo}, editor = {S. Rao Kosaraju and Mike Fellows and Avi Wigderson and John A. Ellis}, title = {A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension}, booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada}, pages = {327--338}, publisher = {{ACM}}, year = {1992}, url = {https://doi.org/10.1145/129712.129744}, doi = {10.1145/129712.129744}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiM92.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jsyml/AjtaiF90, author = {Mikl{\'{o}}s Ajtai and Ronald Fagin}, title = {Reachability Is Harder for Directed than for Undirected Finite Graphs}, journal = {J. Symb. Log.}, volume = {55}, number = {1}, pages = {113--150}, year = {1990}, url = {https://doi.org/10.2307/2274958}, doi = {10.2307/2274958}, timestamp = {Sun, 28 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jsyml/AjtaiF90.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/dimacs/Ajtai90, author = {Mikl{\'{o}}s Ajtai}, editor = {Jin{-}Yi Cai}, title = {Approximate Counting with Uniform Constant-Depth Circuits}, booktitle = {Advances In Computational Complexity Theory, Proceedings of a {DIMACS} Workshop, New Jersey, USA, December 3-7, 1990}, series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science}, volume = {13}, pages = {1--20}, publisher = {{DIMACS/AMS}}, year = {1990}, url = {https://doi.org/10.1090/dimacs/013/01}, doi = {10.1090/DIMACS/013/01}, timestamp = {Mon, 22 May 2023 16:07:35 +0200}, biburl = {https://dblp.org/rec/conf/dimacs/Ajtai90.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/acr/AjtaiKSS89, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and William L. Steiger and Endre Szemer{\'{e}}di}, title = {Almost Sorting in one Round}, journal = {Adv. Comput. Res.}, volume = {5}, pages = {117--125}, year = {1989}, timestamp = {Tue, 25 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/acr/AjtaiKSS89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/acr/AjtaiW89, author = {Mikl{\'{o}}s Ajtai and Avi Wigderson}, title = {Deterministic Simulation of Probabilistic Constant Depth Circuits}, journal = {Adv. Comput. Res.}, volume = {5}, pages = {199--222}, year = {1989}, timestamp = {Tue, 25 Aug 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/acr/AjtaiW89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/apal/Ajtai89, author = {Mikl{\'{o}}s Ajtai}, title = {First-Order Definability on Finite Structures}, journal = {Ann. Pure Appl. Log.}, volume = {45}, number = {3}, pages = {211--225}, year = {1989}, url = {https://doi.org/10.1016/0168-0072(89)90036-5}, doi = {10.1016/0168-0072(89)90036-5}, timestamp = {Fri, 21 Feb 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/apal/Ajtai89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jcss/AjtaiKSS89, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and William L. Steiger and Endre Szemer{\'{e}}di}, title = {Optimal Parallel Selection has Complexity O(Log Log n)}, journal = {J. Comput. Syst. Sci.}, volume = {38}, number = {1}, pages = {125--133}, year = {1989}, url = {https://doi.org/10.1016/0022-0000(89)90035-4}, doi = {10.1016/0022-0000(89)90035-4}, timestamp = {Tue, 16 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jcss/AjtaiKSS89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/siamdm/AjtaiKKS89, author = {Mikl{\'{o}}s Ajtai and D. Karabeg and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {Sorting in Average Time o(log) n}, journal = {{SIAM} J. Discret. Math.}, volume = {2}, number = {3}, pages = {285--292}, year = {1989}, url = {https://doi.org/10.1137/0402024}, doi = {10.1137/0402024}, timestamp = {Sat, 25 Apr 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/siamdm/AjtaiKKS89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiG89, author = {Mikl{\'{o}}s Ajtai and Yuri Gurevich}, title = {Datalog vs. First-Order Logic}, booktitle = {30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989}, pages = {142--147}, publisher = {{IEEE} Computer Society}, year = {1989}, url = {https://doi.org/10.1109/SFCS.1989.63469}, doi = {10.1109/SFCS.1989.63469}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiG89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/Ajtai88, author = {Mikl{\'{o}}s Ajtai}, title = {A lower bound for finding predecessors in Yao's call probe model}, journal = {Comb.}, volume = {8}, number = {3}, pages = {235--247}, year = {1988}, url = {https://doi.org/10.1007/BF02126797}, doi = {10.1007/BF02126797}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/Ajtai88.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Ajtai88, author = {Mikl{\'{o}}s Ajtai}, title = {The Complexity of the Pigeonhole Principle}, booktitle = {29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988}, pages = {346--355}, publisher = {{IEEE} Computer Society}, year = {1988}, url = {https://doi.org/10.1109/SFCS.1988.21951}, doi = {10.1109/SFCS.1988.21951}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Ajtai88.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiF88, author = {Mikl{\'{o}}s Ajtai and Ronald Fagin}, title = {Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)}, booktitle = {29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988}, pages = {358--367}, publisher = {{IEEE} Computer Society}, year = {1988}, url = {https://doi.org/10.1109/SFCS.1988.21952}, doi = {10.1109/SFCS.1988.21952}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiF88.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jacm/AjtaiG87, author = {Mikl{\'{o}}s Ajtai and Yuri Gurevich}, title = {Monotone versus positive}, journal = {J. {ACM}}, volume = {34}, number = {4}, pages = {1004--1015}, year = {1987}, url = {https://doi.org/10.1145/31846.31852}, doi = {10.1145/31846.31852}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jacm/AjtaiG87.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Ajtai87, author = {Mikl{\'{o}}s Ajtai}, title = {Recursive Construction for 3-Regular Expanders}, booktitle = {28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987}, pages = {295--304}, publisher = {{IEEE} Computer Society}, year = {1987}, url = {https://doi.org/10.1109/SFCS.1987.50}, doi = {10.1109/SFCS.1987.50}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Ajtai87.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiKS87, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, editor = {Alfred V. Aho}, title = {Deterministic Simulation in {LOGSPACE}}, booktitle = {Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing, 1987, New York, New York, {USA}}, pages = {132--140}, publisher = {{ACM}}, year = {1987}, url = {https://doi.org/10.1145/28395.28410}, doi = {10.1145/28395.28410}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiKS87.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiBHKPRST86, author = {Mikl{\'{o}}s Ajtai and L{\'{a}}szl{\'{o}} Babai and P{\'{e}}ter Hajnal and J{\'{a}}nos Koml{\'{o}}s and Pavel Pudl{\'{a}}k and Vojtech R{\"{o}}dl and Endre Szemer{\'{e}}di and Gy{\"{o}}rgy Tur{\'{a}}n}, editor = {Juris Hartmanis}, title = {Two lower bounds for branching programs}, booktitle = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, {USA}}, pages = {30--38}, publisher = {{ACM}}, year = {1986}, url = {https://doi.org/10.1145/12130.12134}, doi = {10.1145/12130.12134}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiBHKPRST86.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiKSS86, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and William L. Steiger and Endre Szemer{\'{e}}di}, editor = {Juris Hartmanis}, title = {Deterministic Selection in O(log log {N)} Parallel Time}, booktitle = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, {USA}}, pages = {188--195}, publisher = {{ACM}}, year = {1986}, url = {https://doi.org/10.1145/12130.12149}, doi = {10.1145/12130.12149}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiKSS86.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiW85, author = {Mikl{\'{o}}s Ajtai and Avi Wigderson}, title = {Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)}, booktitle = {26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985}, pages = {11--19}, publisher = {{IEEE} Computer Society}, year = {1985}, url = {https://doi.org/10.1109/SFCS.1985.19}, doi = {10.1109/SFCS.1985.19}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiW85.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiKT84, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and G{\'{a}}bor E. Tusn{\'{a}}dy}, title = {On optimal matchings}, journal = {Comb.}, volume = {4}, number = {4}, pages = {259--264}, year = {1984}, url = {https://doi.org/10.1007/BF02579135}, doi = {10.1007/BF02579135}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiKT84.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/iandc/AjtaiFK84, author = {Mikl{\'{o}}s Ajtai and Michael L. Fredman and J{\'{a}}nos Koml{\'{o}}s}, title = {Hash Functions for Priority Queues}, journal = {Inf. Control.}, volume = {63}, number = {3}, pages = {217--225}, year = {1984}, url = {https://doi.org/10.1016/S0019-9958(84)80015-7}, doi = {10.1016/S0019-9958(84)80015-7}, timestamp = {Fri, 12 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/iandc/AjtaiFK84.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiB84, author = {Mikl{\'{o}}s Ajtai and Michael Ben{-}Or}, editor = {Richard A. DeMillo}, title = {A Theorem on Probabilistic Constant Depth Computations}, booktitle = {Proceedings of the 16th Annual {ACM} Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, {USA}}, pages = {471--474}, publisher = {{ACM}}, year = {1984}, url = {https://doi.org/10.1145/800057.808715}, doi = {10.1145/800057.808715}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiB84.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/apal/Ajtai83, author = {Mikl{\'{o}}s Ajtai}, title = {{\(\sum\)}\({}^{\mbox{1}}\)\({}_{\mbox{1}}\)-Formulae on finite structures}, journal = {Ann. Pure Appl. Log.}, volume = {24}, number = {1}, pages = {1--48}, year = {1983}, url = {https://doi.org/10.1016/0168-0072(83)90038-6}, doi = {10.1016/0168-0072(83)90038-6}, timestamp = {Fri, 21 Feb 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/apal/Ajtai83.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiKS83, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {Sorting in c log n parallel sets}, journal = {Comb.}, volume = {3}, number = {1}, pages = {1--19}, year = {1983}, url = {https://doi.org/10.1007/BF02579338}, doi = {10.1007/BF02579338}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiKS83.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AjtaiFK83, author = {Mikl{\'{o}}s Ajtai and Michael L. Fredman and J{\'{a}}nos Koml{\'{o}}s}, title = {Hash Functions for Priority Queues}, booktitle = {24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983}, pages = {299--303}, publisher = {{IEEE} Computer Society}, year = {1983}, url = {https://doi.org/10.1109/SFCS.1983.24}, doi = {10.1109/SFCS.1983.24}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AjtaiFK83.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/AjtaiKS83, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, 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 = {An O(n log n) Sorting Network}, booktitle = {Proceedings of the 15th Annual {ACM} Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, {USA}}, pages = {1--9}, publisher = {{ACM}}, year = {1983}, url = {https://doi.org/10.1145/800061.808726}, doi = {10.1145/800061.808726}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/AjtaiKS83.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiKS82, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {Largest random component of a k-cube}, journal = {Comb.}, volume = {2}, number = {1}, pages = {1--7}, year = {1982}, url = {https://doi.org/10.1007/BF02579276}, doi = {10.1007/BF02579276}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiKS82.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jct/AjtaiKPSS82, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Janos Pintz and Joel Spencer and Endre Szemer{\'{e}}di}, title = {Extremal Uncrowded Hypergraphs}, journal = {J. Comb. Theory, Ser. {A}}, volume = {32}, number = {3}, pages = {321--335}, year = {1982}, url = {https://doi.org/10.1016/0097-3165(82)90049-8}, doi = {10.1016/0097-3165(82)90049-8}, timestamp = {Tue, 01 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jct/AjtaiKPSS82.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiKS81, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {The longest path in a random graph}, journal = {Comb.}, volume = {1}, number = {1}, pages = {1--12}, year = {1981}, url = {https://doi.org/10.1007/BF02579172}, doi = {10.1007/BF02579172}, timestamp = {Wed, 22 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiKS81.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/combinatorica/AjtaiEKS81, author = {Mikl{\'{o}}s Ajtai and Paul Erd{\"{o}}s and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {On Tur{\'{a}}ns theorem for sparse graphs}, journal = {Comb.}, volume = {1}, number = {4}, pages = {313--317}, year = {1981}, url = {https://doi.org/10.1007/BF02579451}, doi = {10.1007/BF02579451}, timestamp = {Tue, 01 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/combinatorica/AjtaiEKS81.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/ejc/AjtaiKS81, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {A Dense Infinite Sidon Sequence}, journal = {Eur. J. Comb.}, volume = {2}, number = {1}, pages = {1--11}, year = {1981}, url = {https://doi.org/10.1016/S0195-6698(81)80014-5}, doi = {10.1016/S0195-6698(81)80014-5}, timestamp = {Tue, 01 Jun 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/ejc/AjtaiKS81.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jct/AjtaiKS80, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {A Note on Ramsey Numbers}, journal = {J. Comb. Theory, Ser. {A}}, volume = {29}, number = {3}, pages = {354--360}, year = {1980}, url = {https://doi.org/10.1016/0097-3165(80)90030-8}, doi = {10.1016/0097-3165(80)90030-8}, timestamp = {Tue, 16 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jct/AjtaiKS80.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/ipl/AjtaiKS78, author = {Mikl{\'{o}}s Ajtai and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di}, title = {There is no Fast Single Hashing Algorithm}, journal = {Inf. Process. Lett.}, volume = {7}, number = {6}, pages = {270--273}, year = {1978}, url = {https://doi.org/10.1016/0020-0190(78)90014-5}, doi = {10.1016/0020-0190(78)90014-5}, timestamp = {Fri, 26 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/ipl/AjtaiKS78.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.