Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Mario Szegedy
@article{DBLP:journals/cgt/SzegedyY23,
author = {Mario Szegedy and
Jingjin Yu},
title = {An Initial Study of Budgeted Steiner Networks},
journal = {Comput. Geom. Topol.},
volume = {2},
number = {2},
pages = {4:1--4:13},
year = {2023},
url = {https://www.cgt-journal.org/index.php/cgt/article/view/26},
timestamp = {Mon, 19 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cgt/SzegedyY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijrr/SzegedyY23,
author = {Mario Szegedy and
Jingjin Yu},
title = {Rubik Tables and object rearrangement},
journal = {Int. J. Robotics Res.},
volume = {42},
number = {6},
pages = {459--472},
year = {2023},
url = {https://doi.org/10.1177/02783649211059844},
doi = {10.1177/02783649211059844},
timestamp = {Sat, 05 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijrr/SzegedyY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@book{DBLP:books/ws/SzegedyNL22,
author = {Mario Szegedy and
Ilan Newman and
Troy Lee},
title = {Query Complexity},
publisher = {WorldScientific},
year = {2022},
url = {https://doi.org/10.1142/10525},
doi = {10.1142/10525},
isbn = {9789813223202},
timestamp = {Wed, 31 Mar 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/ws/SzegedyNL22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/allerton/GuoFSY22,
author = {Teng Guo and
Si Wei Feng and
Mario Szegedy and
Jingjin Yu},
title = {Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning},
booktitle = {58th Annual Allerton Conference on Communication, Control, and Computing,
Allerton 2022, Monticello, IL, USA, September 27-30, 2022},
pages = {1--4},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/Allerton49937.2022.9929323},
doi = {10.1109/ALLERTON49937.2022.9929323},
timestamp = {Fri, 11 Nov 2022 16:53:12 +0100},
biburl = {https://dblp.org/rec/conf/allerton/GuoFSY22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cccg/YuS22,
author = {Jingjin Yu and
Mario Szegedy},
editor = {Yeganeh Bahoo and
Konstantinos Georgiou},
title = {Budgeted Steiner Networks: Three Terminals with Equal Path Weights},
booktitle = {Proceedings of the 34th Canadian Conference on Computational Geometry,
{CCCG} 2022, Toronto Metropolitan University, Toronto, Ontario, Canada,
August 25-27, 2022},
pages = {322--329},
year = {2022},
timestamp = {Wed, 23 Nov 2022 15:41:57 +0100},
biburl = {https://dblp.org/rec/conf/cccg/YuS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2201-11602,
author = {Mario Szegedy and
Jingjin Yu},
title = {Budgeted Steiner Networks: Three Terminals with Equal Path Weights},
journal = {CoRR},
volume = {abs/2201.11602},
year = {2022},
url = {https://arxiv.org/abs/2201.11602},
eprinttype = {arXiv},
eprint = {2201.11602},
timestamp = {Tue, 01 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2201-11602.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2205-04535,
author = {Ramis Movassagh and
Mario Szegedy and
Guanyang Wang},
title = {Repeated Averages on Graphs},
journal = {CoRR},
volume = {abs/2205.04535},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2205.04535},
doi = {10.48550/ARXIV.2205.04535},
eprinttype = {arXiv},
eprint = {2205.04535},
timestamp = {Thu, 12 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2205-04535.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2209-11405,
author = {Andrew W. Cross and
Zhiyang He and
Anand Natarajan and
Mario Szegedy and
Guanyu Zhu},
title = {Quantum Locally Testable Code with Exotic Parameters},
journal = {CoRR},
volume = {abs/2209.11405},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2209.11405},
doi = {10.48550/ARXIV.2209.11405},
eprinttype = {arXiv},
eprint = {2209.11405},
timestamp = {Tue, 31 Oct 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2209-11405.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ncs/HuangZNN0CGWWZK21,
author = {Cupjin Huang and
Fang Zhang and
Michael Newman and
Xiaotong Ni and
Dawei Ding and
Junjie Cai and
Xun Gao and
Tenghui Wang and
Feng Wu and
Gengyan Zhang and
Hsiang{-}Sheng Ku and
Zhengxiong Tian and
Junyin Wu and
Haihong Xu and
Huanjun Yu and
Bo Yuan and
Mario Szegedy and
Yaoyun Shi and
Hui{-}Hai Zhao and
Chunqing Deng and
Jianxin Chen},
title = {Efficient parallelization of tensor network contraction for simulating
quantum computation},
journal = {Nat. Comput. Sci.},
volume = {1},
number = {9},
pages = {578--587},
year = {2021},
url = {https://doi.org/10.1038/s43588-021-00119-7},
doi = {10.1038/S43588-021-00119-7},
timestamp = {Mon, 15 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ncs/HuangZNN0CGWWZK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wafr/SzegedyY21,
author = {Mario Szegedy and
Jingjin Yu},
editor = {Steven M. LaValle and
Ming Lin and
Timo Ojala and
Dylan A. Shell and
Jingjin Yu},
title = {On Rearrangement of Items Stored in Stacks},
booktitle = {Algorithmic Foundations of Robotics XIV, Proceedings of the Fourteenth
Workshop on the Algorithmic Foundations of Robotics, {WAFR} 2021,
Oulu, Finland, June 21-23, 2021},
series = {Springer Proceedings in Advanced Robotics},
volume = {17},
pages = {518--533},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-66723-8\_31},
doi = {10.1007/978-3-030-66723-8\_31},
timestamp = {Thu, 09 Sep 2021 16:00:49 +0200},
biburl = {https://dblp.org/rec/conf/wafr/SzegedyY21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/HuangNS20,
author = {Cupjin Huang and
Michael Newman and
Mario Szegedy},
title = {Explicit Lower Bounds on Strong Quantum Simulation},
journal = {{IEEE} Trans. Inf. Theory},
volume = {66},
number = {9},
pages = {5585--5600},
year = {2020},
url = {https://doi.org/10.1109/TIT.2020.3004427},
doi = {10.1109/TIT.2020.3004427},
timestamp = {Sat, 19 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tit/HuangNS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-04979,
author = {Mario Szegedy and
Jingjin Yu},
title = {On Rearrangement of Items Stored in Stacks},
journal = {CoRR},
volume = {abs/2002.04979},
year = {2020},
url = {https://arxiv.org/abs/2002.04979},
eprinttype = {arXiv},
eprint = {2002.04979},
timestamp = {Fri, 14 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-04979.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1902-04764,
author = {Cupjin Huang and
Michael Newman and
Mario Szegedy},
title = {Explicit lower bounds on strong simulation of quantum circuits in
terms of {\textdollar}T{\textdollar}-gate count},
journal = {CoRR},
volume = {abs/1902.04764},
year = {2019},
url = {http://arxiv.org/abs/1902.04764},
eprinttype = {arXiv},
eprint = {1902.04764},
timestamp = {Tue, 21 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1902-04764.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-10368,
author = {Cupjin Huang and
Michael Newman and
Mario Szegedy},
title = {Explicit lower bounds on strong quantum simulation},
journal = {CoRR},
volume = {abs/1804.10368},
year = {2018},
url = {http://arxiv.org/abs/1804.10368},
eprinttype = {arXiv},
eprint = {1804.10368},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-10368.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pomacs/LiGHCCZS17,
author = {Lingda Li and
Robel Geda and
Ari B. Hayes and
Yan{-}Hao Chen and
Pranav Chaudhari and
Eddy Z. Zhang and
Mario Szegedy},
title = {A Simple Yet Effective Balanced Edge Partition Model for Parallel
Computing},
journal = {Proc. {ACM} Meas. Anal. Comput. Syst.},
volume = {1},
number = {1},
pages = {14:1--14:21},
year = {2017},
url = {https://doi.org/10.1145/3084451},
doi = {10.1145/3084451},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pomacs/LiGHCCZS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alenex/CatarataCSSVZ17,
author = {Jan Dean Catarata and
Scott Corbett and
Harry Stern and
Mario Szegedy and
Tom{\'{a}}s Vyskocil and
Zheng Zhang},
editor = {S{\'{a}}ndor P. Fekete and
Vijaya Ramachandran},
title = {The Moser-Tardos Resample algorithm: Where is the limit? (an experimental
inquiry)},
booktitle = {Proceedings of the Ninteenth Workshop on Algorithm Engineering and
Experiments, {ALENEX} 2017, Barcelona, Spain, Hotel Porta Fira, January
17-18, 2017},
pages = {159--171},
publisher = {{SIAM}},
year = {2017},
url = {https://doi.org/10.1137/1.9781611974768.13},
doi = {10.1137/1.9781611974768.13},
timestamp = {Fri, 02 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/alenex/CatarataCSSVZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigmetrics/LiGHCCZS17,
author = {Lingda Li and
Robel Geda and
Ari B. Hayes and
Yan{-}Hao Chen and
Pranav Chaudhari and
Eddy Z. Zhang and
Mario Szegedy},
editor = {Bruce E. Hajek and
Sewoong Oh and
Augustin Chaintreau and
Leana Golubchik and
Zhi{-}Li Zhang},
title = {A Simple Yet Effective Balanced Edge Partition Model for Parallel
Computing},
booktitle = {Proceedings of the 2017 {ACM} {SIGMETRICS} / International Conference
on Measurement and Modeling of Computer Systems, Urbana-Champaign,
IL, USA, June 05 - 09, 2017},
pages = {6},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3078505.3078520},
doi = {10.1145/3078505.3078520},
timestamp = {Fri, 30 Jul 2021 16:13:32 +0200},
biburl = {https://dblp.org/rec/conf/sigmetrics/LiGHCCZS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/HalldorssonHLS16,
author = {Bjarni V. Halld{\'{o}}rsson and
Magn{\'{u}}s M. Halld{\'{o}}rsson and
Elena Losievskaja and
Mario Szegedy},
title = {Streaming Algorithms for Independent Sets in Sparse Hypergraphs},
journal = {Algorithmica},
volume = {76},
number = {2},
pages = {490--501},
year = {2016},
url = {https://doi.org/10.1007/s00453-015-0051-5},
doi = {10.1007/S00453-015-0051-5},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/HalldorssonHLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ejc/KunS16,
author = {G{\'{a}}bor Kun and
Mario Szegedy},
title = {A new line of attack on the dichotomy conjecture},
journal = {Eur. J. Comb.},
volume = {52},
pages = {338--367},
year = {2016},
url = {https://doi.org/10.1016/j.ejc.2015.07.011},
doi = {10.1016/J.EJC.2015.07.011},
timestamp = {Sun, 22 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ejc/KunS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/NayakRS16,
author = {Ashwin Nayak and
Peter C. Richter and
Mario Szegedy},
title = {Quantum Analogues of Markov Chains},
booktitle = {Encyclopedia of Algorithms},
pages = {1683--1691},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_302},
doi = {10.1007/978-1-4939-2864-4\_302},
timestamp = {Mon, 18 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/NayakRS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/LiHHZSS16,
author = {Lingda Li and
Ari B. Hayes and
Stephen A. Hackler and
Eddy Z. Zhang and
Mario Szegedy and
Shuaiwen Leon Song},
title = {A Graph-based Model for {GPU} Caching Problems},
journal = {CoRR},
volume = {abs/1605.02043},
year = {2016},
url = {http://arxiv.org/abs/1605.02043},
eprinttype = {arXiv},
eprint = {1605.02043},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/LiHHZSS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/SzegedyX15,
author = {Mario Szegedy and
Yixin Xu},
title = {Impossibility Theorems and the Universal Algebraic Toolkit},
journal = {CoRR},
volume = {abs/1506.01315},
year = {2015},
url = {http://arxiv.org/abs/1506.01315},
eprinttype = {arXiv},
eprint = {1506.01315},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/SzegedyX15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Szegedy15,
author = {Mario Szegedy},
title = {An {\textdollar}O(n{\^{}}\{0.4732\}){\textdollar} upper bound on the
complexity of the {GKS} communication game},
journal = {CoRR},
volume = {abs/1506.06456},
year = {2015},
url = {http://arxiv.org/abs/1506.06456},
eprinttype = {arXiv},
eprint = {1506.06456},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Szegedy15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaim/ChiuSWX14,
author = {Well Y. Chiu and
Mario Szegedy and
Chengu Wang and
Yixin Xu},
editor = {Qianping Gu and
Pavol Hell and
Boting Yang},
title = {The Garden Hose Complexity for the Equality Function},
booktitle = {Algorithmic Aspects in Information and Management - 10th International
Conference, {AAIM} 2014, Vancouver, BC, Canada, July 8-11, 2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8546},
pages = {112--123},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-07956-1\_11},
doi = {10.1007/978-3-319-07956-1\_11},
timestamp = {Tue, 14 May 2019 10:00:41 +0200},
biburl = {https://dblp.org/rec/conf/aaim/ChiuSWX14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AharonovHLNSV14,
author = {Dorit Aharonov and
Aram W. Harrow and
Zeph Landau and
Daniel Nagaj and
Mario Szegedy and
Umesh V. Vazirani},
title = {Local Tests of Global Entanglement and a Counterexample to the Generalized
Area Law},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {246--255},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.34},
doi = {10.1109/FOCS.2014.34},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AharonovHLNSV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/crypto/KiltzPS13,
author = {Eike Kiltz and
Krzysztof Pietrzak and
Mario Szegedy},
editor = {Ran Canetti and
Juan A. Garay},
title = {Digital Signatures with Minimal Overhead from Indifferentiable Random
Invertible Functions},
booktitle = {Advances in Cryptology - {CRYPTO} 2013 - 33rd Annual Cryptology Conference,
Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {8042},
pages = {571--588},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40041-4\_31},
doi = {10.1007/978-3-642-40041-4\_31},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/crypto/KiltzPS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Szegedy13,
author = {Mario Szegedy},
editor = {Andrei A. Bulatov and
Arseny M. Shur},
title = {The Lov{\'{a}}sz Local Lemma - {A} Survey},
booktitle = {Computer Science - Theory and Applications - 8th International Computer
Science Symposium in Russia, {CSR} 2013, Ekaterinburg, Russia, June
25-29, 2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7913},
pages = {1--11},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-38536-0\_1},
doi = {10.1007/978-3-642-38536-0\_1},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/csr/Szegedy13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChiuSWX13,
author = {Well Y. Chiu and
Mario Szegedy and
Chengu Wang and
Yixin Xu},
title = {The Garden Hose Complexity for the Equality Function},
journal = {CoRR},
volume = {abs/1312.7222},
year = {2013},
url = {http://arxiv.org/abs/1312.7222},
eprinttype = {arXiv},
eprint = {1312.7222},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChiuSWX13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KolipakaSX12,
author = {Kashyap Babu Rao Kolipaka and
Mario Szegedy and
Yixin Xu},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {A Sharper Local Lemma with Improved Applications},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 15th International Workshop, {APPROX} 2012, and 16th
International Workshop, {RANDOM} 2012, Cambridge, MA, USA, August
15-17, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7408},
pages = {603--614},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_51},
doi = {10.1007/978-3-642-32512-0\_51},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KolipakaSX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/PoloczekS12,
author = {Matthias Poloczek and
Mario Szegedy},
title = {Randomized Greedy Algorithms for the Maximum Matching Problem with
New Analysis},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2012, New Brunswick, NJ, USA, October 20-23, 2012},
pages = {708--717},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/FOCS.2012.20},
doi = {10.1109/FOCS.2012.20},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/PoloczekS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/HalldorssonSSW12,
author = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Xiaoming Sun and
Mario Szegedy and
Chengu Wang},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Streaming and Communication Complexity of Clique Approximation},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {449--460},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_38},
doi = {10.1007/978-3-642-31594-7\_38},
timestamp = {Wed, 26 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/HalldorssonSSW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigecom/CaragiannisESY12,
author = {Ioannis Caragiannis and
Edith Elkind and
Mario Szegedy and
Lan Yu},
editor = {Boi Faltings and
Kevin Leyton{-}Brown and
Panos Ipeirotis},
title = {Mechanism design: from partial to probabilistic verification},
booktitle = {Proceedings of the 13th {ACM} Conference on Electronic Commerce, {EC}
2012, Valencia, Spain, June 4-8, 2012},
pages = {266--283},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2229012.2229035},
doi = {10.1145/2229012.2229035},
timestamp = {Tue, 27 Nov 2018 11:56:48 +0100},
biburl = {https://dblp.org/rec/conf/sigecom/CaragiannisESY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/KiltzPS12,
author = {Eike Kiltz and
Krzysztof Pietrzak and
Mario Szegedy},
title = {Digital Signatures with Minimal Overhead},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {658},
year = {2012},
url = {http://eprint.iacr.org/2012/658},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/KiltzPS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dmtcs/SeressS11,
author = {{\'{A}}kos Seress and
Mario Szegedy},
title = {Combinatorics, Groups, Algorithms, and Complexity: Conference in honor
of Laci Babai's 60th birthday},
journal = {Discret. Math. Theor. Comput. Sci.},
volume = {13},
number = {4},
pages = {1--4},
year = {2011},
url = {https://doi.org/10.46298/dmtcs.529},
doi = {10.46298/DMTCS.529},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dmtcs/SeressS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeeMRSS11,
author = {Troy Lee and
Rajat Mittal and
Ben W. Reichardt and
Robert Spalek and
Mario Szegedy},
editor = {Rafail Ostrovsky},
title = {Quantum Query Complexity of State Conversion},
booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
2011, Palm Springs, CA, USA, October 22-25, 2011},
pages = {344--353},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/FOCS.2011.75},
doi = {10.1109/FOCS.2011.75},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LeeMRSS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KolipakaS11,
author = {Kashyap Babu Rao Kolipaka and
Mario Szegedy},
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {Moser and tardos meet Lov{\'{a}}sz},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages = {235--244},
publisher = {{ACM}},
year = {2011},
url = {https://doi.org/10.1145/1993636.1993669},
doi = {10.1145/1993636.1993669},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KolipakaS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cccg/SteigerSZ10,
author = {William Steiger and
Mario Szegedy and
Jihui Zhao},
title = {Six-way equipartitioning by three lines in the plane},
booktitle = {Proceedings of the 22nd Annual Canadian Conference on Computational
Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010},
pages = {277--280},
year = {2010},
url = {http://cccg.ca/proceedings/2010/paper73.pdf},
timestamp = {Wed, 12 May 2021 14:19:37 +0200},
biburl = {https://dblp.org/rec/conf/cccg/SteigerSZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/HalldorssonHLS10,
author = {Bjarni V. Halld{\'{o}}rsson and
Magn{\'{u}}s M. Halld{\'{o}}rsson and
Elena Losievskaja and
Mario Szegedy},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {Streaming Algorithms for Independent Sets},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {641--652},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_54},
doi = {10.1007/978-3-642-14165-2\_54},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/HalldorssonHLS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/SanthaS09,
author = {Miklos Santha and
Mario Szegedy},
title = {Quantum and Classical Query Complexities of Local Search Are Polynomially
Related},
journal = {Algorithmica},
volume = {55},
number = {3},
pages = {557--575},
year = {2009},
url = {https://doi.org/10.1007/s00453-008-9169-z},
doi = {10.1007/S00453-008-9169-Z},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/SanthaS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/comgeo/MukkamalaS09,
author = {Padmini Mukkamala and
Mario Szegedy},
title = {Geometric representation of cubic graphs with four directions},
journal = {Comput. Geom.},
volume = {42},
number = {9},
pages = {842--851},
year = {2009},
url = {https://doi.org/10.1016/j.comgeo.2009.01.005},
doi = {10.1016/J.COMGEO.2009.01.005},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/comgeo/MukkamalaS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/ChenPST09,
author = {Xiaomin Chen and
J{\'{a}}nos Pach and
Mario Szegedy and
G{\'{a}}bor Tardos},
title = {Delaunay graphs of point sets in the plane with respect to axis-parallel
rectangles},
journal = {Random Struct. Algorithms},
volume = {34},
number = {1},
pages = {11--23},
year = {2009},
url = {https://doi.org/10.1002/rsa.20246},
doi = {10.1002/RSA.20246},
timestamp = {Fri, 15 Sep 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/ChenPST09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/RolandS09,
author = {J{\'{e}}r{\'{e}}mie Roland and
Mario Szegedy},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {Amortized Communication Complexity of Distributions},
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 = {738--749},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_61},
doi = {10.1007/978-3-642-02927-1\_61},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/RolandS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KunS09,
author = {G{\'{a}}bor Kun and
Mario Szegedy},
editor = {Michael Mitzenmacher},
title = {A new line of attack on the dichotomy conjecture},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {725--734},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536512},
doi = {10.1145/1536414.1536512},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KunS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KunS09,
author = {G{\'{a}}bor Kun and
Mario Szegedy},
title = {A {NEW} {LINE} {OF} {ATTACK} {ON} {THE} {DICHOTOMY} {CONJECTURE}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-059}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/059},
eprinttype = {ECCC},
eprint = {TR09-059},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KunS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/AzimianS08,
author = {Kooshiar Azimian and
Mario Szegedy},
editor = {Eduardo Sany Laber and
Claudson F. Bornstein and
Loana Tito Nogueira and
Lu{\'{e}}rbio Faria},
title = {Parallel Repetition of the Odd Cycle Game},
booktitle = {{LATIN} 2008: Theoretical Informatics, 8th Latin American Symposium,
B{\'{u}}zios, Brazil, April 7-11, 2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4957},
pages = {676--686},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-78773-0\_58},
doi = {10.1007/978-3-540-78773-0\_58},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/AzimianS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenPST08,
author = {Xiaomin Chen and
J{\'{a}}nos Pach and
Mario Szegedy and
G{\'{a}}bor Tardos},
editor = {Shang{-}Hua Teng},
title = {Delaunay graphs of point sets in the plane with respect to axis-parallel
rectangles},
booktitle = {Proceedings of the Nineteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2008, San Francisco, California, USA, January 20-22,
2008},
pages = {94--101},
publisher = {{SIAM}},
year = {2008},
url = {http://dl.acm.org/citation.cfm?id=1347082.1347093},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenPST08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/RichterS08,
author = {Peter C. Richter and
Mario Szegedy},
editor = {Ming{-}Yang Kao},
title = {Quantization of Markov Chains},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_302},
doi = {10.1007/978-0-387-30162-4\_302},
timestamp = {Thu, 27 Jun 2019 16:25:31 +0200},
biburl = {https://dblp.org/rec/reference/algo/RichterS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/MagniezSS07,
author = {Fr{\'{e}}d{\'{e}}ric Magniez and
Miklos Santha and
Mario Szegedy},
title = {Quantum Algorithms for the Triangle Problem},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {2},
pages = {413--424},
year = {2007},
url = {https://doi.org/10.1137/050643684},
doi = {10.1137/050643684},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/MagniezSS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/SzegedyT07,
author = {Mario Szegedy and
Mikkel Thorup},
editor = {Lars Arge and
Michael Hoffmann and
Emo Welzl},
title = {On the Variance of Subset Sum Estimation},
booktitle = {Algorithms - {ESA} 2007, 15th Annual European Symposium, Eilat, Israel,
October 8-10, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4698},
pages = {75--86},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-75520-3\_9},
doi = {10.1007/978-3-540-75520-3\_9},
timestamp = {Tue, 14 May 2019 10:00:54 +0200},
biburl = {https://dblp.org/rec/conf/esa/SzegedyT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/MittalS07,
author = {Rajat Mittal and
Mario Szegedy},
editor = {Erzs{\'{e}}bet Csuhaj{-}Varj{\'{u}} and
Zolt{\'{a}}n {\'{E}}sik},
title = {Product Rules in Semidefinite Programming},
booktitle = {Fundamentals of Computation Theory, 16th International Symposium,
{FCT} 2007, Budapest, Hungary, August 27-30, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4639},
pages = {435--445},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74240-1\_38},
doi = {10.1007/978-3-540-74240-1\_38},
timestamp = {Wed, 26 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fct/MittalS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChattopadhyayKKSTT07,
author = {Arkadev Chattopadhyay and
Andreas Krebs and
Michal Kouck{\'{y}} and
Mario Szegedy and
Pascal Tesson and
Denis Th{\'{e}}rien},
editor = {Wolfgang Thomas and
Pascal Weil},
title = {Languages with Bounded Multiparty Communication Complexity},
booktitle = {{STACS} 2007, 24th Annual Symposium on Theoretical Aspects of Computer
Science, Aachen, Germany, February 22-24, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4393},
pages = {500--511},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-70918-3\_43},
doi = {10.1007/978-3-540-70918-3\_43},
timestamp = {Thu, 02 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/ChattopadhyayKKSTT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/crc/Szegedy07,
author = {Mario Szegedy},
editor = {Teofilo F. Gonzalez},
title = {Hardness of Approximation},
booktitle = {Handbook of Approximation Algorithms and Metaheuristics},
publisher = {Chapman and Hall/CRC},
year = {2007},
url = {https://doi.org/10.1201/9781420010749.ch17},
doi = {10.1201/9781420010749.CH17},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/crc/Szegedy07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0702029,
author = {Mario Szegedy and
Mikkel Thorup},
title = {On the variance of subset sum estimation},
journal = {CoRR},
volume = {abs/cs/0702029},
year = {2007},
url = {http://arxiv.org/abs/cs/0702029},
eprinttype = {arXiv},
eprint = {cs/0702029},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0702029.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/LaplanteLS06,
author = {Sophie Laplante and
Troy Lee and
Mario Szegedy},
title = {The Quantum Adversary Method and Classical Formula Size Lower Bounds},
journal = {Comput. Complex.},
volume = {15},
number = {2},
pages = {163--196},
year = {2006},
url = {https://doi.org/10.1007/s00037-006-0212-7},
doi = {10.1007/S00037-006-0212-7},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/LaplanteLS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/SpalekS06,
author = {Robert Spalek and
Mario Szegedy},
title = {All Quantum Adversary Methods are Equivalent},
journal = {Theory Comput.},
volume = {2},
number = {1},
pages = {1--18},
year = {2006},
url = {https://doi.org/10.4086/toc.2006.v002a001},
doi = {10.4086/TOC.2006.V002A001},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/SpalekS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sat/ChenIJSS06,
author = {Su Chen and
Tomasz Imielinski and
Karin Johnsgard and
Donald Smith and
Mario Szegedy},
editor = {Armin Biere and
Carla P. Gomes},
title = {A Dichotomy Theorem for Typed Constraint Satisfaction Problems},
booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2006, 9th
International Conference, Seattle, WA, USA, August 12-15, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4121},
pages = {226--239},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11814948\_23},
doi = {10.1007/11814948\_23},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/sat/ChenIJSS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Szegedy06,
author = {Mario Szegedy},
editor = {Jon M. Kleinberg},
title = {The {DLT} priority sampling is essentially optimal},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {150--158},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132539},
doi = {10.1145/1132516.1132539},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Szegedy06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChattopadhyayKKSTT06,
author = {Arkadev Chattopadhyay and
Michal Kouck{\'{y}} and
Andreas Krebs and
Mario Szegedy and
Pascal Tesson and
Denis Th{\'{e}}rien},
title = {Languages with Bounded Multiparty Communication Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-117}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-117/index.html},
eprinttype = {ECCC},
eprint = {TR06-117},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChattopadhyayKKSTT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/LaplanteLS05,
author = {Sophie Laplante and
Troy Lee and
Mario Szegedy},
title = {The Quantum Adversary Method and Classical Formula Size Lower Bounds},
booktitle = {20th Annual {IEEE} Conference on Computational Complexity {(CCC} 2005),
11-15 June 2005, San Jose, CA, {USA}},
pages = {76--90},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/CCC.2005.29},
doi = {10.1109/CCC.2005.29},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/LaplanteLS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/ChenSW05,
author = {Xiaomin Chen and
Mario Szegedy and
Lei Wang},
editor = {Lusheng Wang},
title = {Optimally Balanced Forward Degree Sequence},
booktitle = {Computing and Combinatorics, 11th Annual International Conference,
{COCOON} 2005, Kunming, China, August 16-29, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3595},
pages = {680--689},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11533719\_69},
doi = {10.1007/11533719\_69},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/ChenSW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/SpalekS05,
author = {Robert Spalek and
Mario Szegedy},
editor = {Lu{\'{\i}}s Caires and
Giuseppe F. Italiano and
Lu{\'{\i}}s Monteiro and
Catuscia Palamidessi and
Moti Yung},
title = {All Quantum Adversary Methods Are Equivalent},
booktitle = {Automata, Languages and Programming, 32nd International Colloquium,
{ICALP} 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3580},
pages = {1299--1311},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11523468\_105},
doi = {10.1007/11523468\_105},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/SpalekS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/MagniezSS05,
author = {Fr{\'{e}}d{\'{e}}ric Magniez and
Miklos Santha and
Mario Szegedy},
title = {Quantum algorithms for the triangle problem},
booktitle = {Proceedings of the Sixteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2005, Vancouver, British Columbia, Canada, January
23-25, 2005},
pages = {1109--1117},
publisher = {{SIAM}},
year = {2005},
url = {http://dl.acm.org/citation.cfm?id=1070432.1070591},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/MagniezSS05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-001,
author = {Mario Szegedy},
title = {Near optimality of the priority sampling procedure},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-001}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-001/index.html},
eprinttype = {ECCC},
eprint = {TR05-001},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-001.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/BaloghRSSS04,
author = {J{\'{o}}zsef Balogh and
Oded Regev and
Clifford D. Smyth and
William L. Steiger and
Mario Szegedy},
title = {Long Monotone Paths in Line Arrangements},
journal = {Discret. Comput. Geom.},
volume = {32},
number = {2},
pages = {167--176},
year = {2004},
url = {https://doi.org/10.1007/s00454-004-1119-1},
doi = {10.1007/S00454-004-1119-1},
timestamp = {Thu, 27 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dcg/BaloghRSSS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/SzegedyC04,
author = {Mario Szegedy and
Xiaomin Chen},
title = {Computing Boolean functions from multiple faulty copies of input bits},
journal = {Theor. Comput. Sci.},
volume = {321},
number = {1},
pages = {149--170},
year = {2004},
url = {https://doi.org/10.1016/j.tcs.2003.07.001},
doi = {10.1016/J.TCS.2003.07.001},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/SzegedyC04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Szegedy04,
author = {Mario Szegedy},
title = {Quantum Speed-Up of Markov Chain Based Algorithms},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {32--41},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.53},
doi = {10.1109/FOCS.2004.53},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Szegedy04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SanthaS04,
author = {Miklos Santha and
Mario Szegedy},
editor = {L{\'{a}}szl{\'{o}} Babai},
title = {Quantum and classical query complexities of local search are polynomially
related},
booktitle = {Proceedings of the 36th Annual {ACM} Symposium on Theory of Computing,
Chicago, IL, USA, June 13-16, 2004},
pages = {494--501},
publisher = {{ACM}},
year = {2004},
url = {https://doi.org/10.1145/1007352.1007427},
doi = {10.1145/1007352.1007427},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SanthaS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BarnumSS03,
author = {Howard Barnum and
Michael E. Saks and
Mario Szegedy},
title = {Quantum query complexity and semi-definite programming},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {179--193},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214419},
doi = {10.1109/CCC.2003.1214419},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BarnumSS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/compgeom/BaloghRSSS03,
author = {J{\'{o}}zsef Balogh and
Oded Regev and
Clifford D. Smyth and
William L. Steiger and
Mario Szegedy},
editor = {Steven Fortune},
title = {Long monotone paths in line arrangements},
booktitle = {Proceedings of the 19th {ACM} Symposium on Computational Geometry,
San Diego, CA, USA, June 8-10, 2003},
pages = {124--128},
publisher = {{ACM}},
year = {2003},
url = {https://doi.org/10.1145/777792.777812},
doi = {10.1145/777792.777812},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/compgeom/BaloghRSSS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AlonGMS02,
author = {Noga Alon and
Phillip B. Gibbons and
Yossi Matias and
Mario Szegedy},
title = {Tracking Join and Self-Join Sizes in Limited Storage},
journal = {J. Comput. Syst. Sci.},
volume = {64},
number = {3},
pages = {719--747},
year = {2002},
url = {https://doi.org/10.1006/jcss.2001.1813},
doi = {10.1006/JCSS.2001.1813},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/AlonGMS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/SzegedyC02,
author = {Mario Szegedy and
Xiaomin Chen},
editor = {Sergio Rajsbaum},
title = {Computing Boolean Functions from Multiple Faulty Copies of Input Bits},
booktitle = {{LATIN} 2002: Theoretical Informatics, 5th Latin American Symposium,
Cancun, Mexico, April 3-6, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2286},
pages = {539--553},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45995-2\_47},
doi = {10.1007/3-540-45995-2\_47},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/latin/SzegedyC02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jct/AlonFS01,
author = {Noga Alon and
Eldar Fischer and
Mario Szegedy},
title = {Parent-Identifying Codes},
journal = {J. Comb. Theory, Ser. {A}},
volume = {95},
number = {2},
pages = {349--359},
year = {2001},
url = {https://doi.org/10.1006/jcta.2001.3177},
doi = {10.1006/JCTA.2001.3177},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jct/AlonFS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/AlonFKS00,
author = {Noga Alon and
Eldar Fischer and
Michael Krivelevich and
Mario Szegedy},
title = {Efficient Testing of Large Graphs},
journal = {Comb.},
volume = {20},
number = {4},
pages = {451--476},
year = {2000},
url = {https://doi.org/10.1007/s004930070001},
doi = {10.1007/S004930070001},
timestamp = {Tue, 01 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/AlonFKS00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AlonKNS00,
author = {Noga Alon and
Michael Krivelevich and
Ilan Newman and
Mario Szegedy},
title = {Regular Languages are Testable with a Constant Number of Queries},
journal = {{SIAM} J. Comput.},
volume = {30},
number = {6},
pages = {1842--1862},
year = {2000},
url = {https://doi.org/10.1137/S0097539700366528},
doi = {10.1137/S0097539700366528},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/AlonKNS00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/gc/AlonS99,
author = {Noga Alon and
Mario Szegedy},
title = {Large Sets of Nearly Orthogonal Vectors},
journal = {Graphs Comb.},
volume = {15},
number = {1},
pages = {1--4},
year = {1999},
url = {https://doi.org/10.1007/PL00021187},
doi = {10.1007/PL00021187},
timestamp = {Thu, 04 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/gc/AlonS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AlonMS99,
author = {Noga Alon and
Yossi Matias and
Mario Szegedy},
title = {The Space Complexity of Approximating the Frequency Moments},
journal = {J. Comput. Syst. Sci.},
volume = {58},
number = {1},
pages = {137--147},
year = {1999},
url = {https://doi.org/10.1006/jcss.1997.1545},
doi = {10.1006/JCSS.1997.1545},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/AlonMS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonKNS99,
author = {Noga Alon and
Michael Krivelevich and
Ilan Newman and
Mario Szegedy},
title = {Regular Languages Are Testable with a Constant Number of Queries},
booktitle = {40th Annual Symposium on Foundations of Computer Science, {FOCS} '99,
17-18 October, 1999, New York, NY, {USA}},
pages = {645--655},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/SFFCS.1999.814641},
doi = {10.1109/SFFCS.1999.814641},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonKNS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonFKS99,
author = {Noga Alon and
Eldar Fischer and
Michael Krivelevich and
Mario Szegedy},
title = {Efficient Testing of Large Graphs},
booktitle = {40th Annual Symposium on Foundations of Computer Science, {FOCS} '99,
17-18 October, 1999, New York, NY, {USA}},
pages = {656--666},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/SFFCS.1999.814642},
doi = {10.1109/SFFCS.1999.814642},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonFKS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Szegedy99,
author = {Mario Szegedy},
editor = {Jir{\'{\i}} Wiedermann and
Peter van Emde Boas and
Mogens Nielsen},
title = {Many-Valued Logics and Holographic Proofs},
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 = {676--686},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-48523-6\_64},
doi = {10.1007/3-540-48523-6\_64},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Szegedy99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/AlonGMS99,
author = {Noga Alon and
Phillip B. Gibbons and
Yossi Matias and
Mario Szegedy},
editor = {Victor Vianu and
Christos H. Papadimitriou},
title = {Tracking Join and Self-Join Sizes in Limited Storage},
booktitle = {Proceedings of the Eighteenth {ACM} {SIGACT-SIGMOD-SIGART} Symposium
on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
Pennsylvania, {USA}},
pages = {10--20},
publisher = {{ACM} Press},
year = {1999},
url = {https://doi.org/10.1145/303976.303978},
doi = {10.1145/303976.303978},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/pods/AlonGMS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaplanS99,
author = {Haim Kaplan and
Mario Szegedy},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {On-line Complexity of Monotone Set Systems},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {507--516},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314872},
timestamp = {Thu, 05 Jul 2018 07:29:57 +0200},
biburl = {https://dblp.org/rec/conf/soda/KaplanS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohnsonS99,
author = {David S. Johnson and
Mario Szegedy},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {What are the Least Tractable Instances of max Independent Set?},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {927--928},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.315093},
timestamp = {Tue, 01 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/JohnsonS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KaplanSS99,
author = {Haim Kaplan and
Martin Strauss and
Mario Szegedy},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {Just the Fax - Differentiating Voice and Fax Phone Lines Using Call
Billing Data},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {935--936},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314929},
timestamp = {Tue, 19 Dec 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/KaplanSS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/Szegedy99,
author = {Mario Szegedy},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {A Slique Size Bounding Technique with Application to Non-Linear Codes},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {971--972},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314952},
timestamp = {Fri, 07 Dec 2012 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/Szegedy99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/Szegedy99,
author = {Mario Szegedy},
editor = {Christoph Meinel and
Sophie Tison},
title = {In How Many Steps the k Peg Version of the Towers of Hanoi Game Can
Be Solved?},
booktitle = {{STACS} 99, 16th Annual Symposium on Theoretical Aspects of Computer
Science, Trier, Germany, March 4-6, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1563},
pages = {356--361},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-49116-3\_33},
doi = {10.1007/3-540-49116-3\_33},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/Szegedy99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/AroraLMSS98,
author = {Sanjeev Arora and
Carsten Lund and
Rajeev Motwani and
Madhu Sudan and
Mario Szegedy},
title = {Proof Verification and the Hardness of Approximation Problems},
journal = {J. {ACM}},
volume = {45},
number = {3},
pages = {501--555},
year = {1998},
url = {https://doi.org/10.1145/278298.278306},
doi = {10.1145/278298.278306},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/AroraLMSS98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Szegedy98,
author = {Mario Szegedy},
title = {Algorithms to Tile the Infinite Grid with Finite Clusters},
booktitle = {39th Annual Symposium on Foundations of Computer Science, {FOCS} '98,
November 8-11, 1998, Palo Alto, California, {USA}},
pages = {137--147},
publisher = {{IEEE} Computer Society},
year = {1998},
url = {https://doi.org/10.1109/SFCS.1998.743437},
doi = {10.1109/SFCS.1998.743437},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Szegedy98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR98-008,
author = {Sanjeev Arora and
Carsten Lund and
Rajeev Motwani and
Madhu Sudan and
Mario Szegedy},
title = {Proof verification and the hardness of approximation problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR98-008}},
year = {1998},
url = {https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-008/index.html},
eprinttype = {ECCC},
eprint = {TR98-008},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR98-008.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/LovaszPS97,
author = {L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and
J{\'{a}}nos Pach and
Mario Szegedy},
title = {On Conway's Thrackle Conjecture},
journal = {Discret. Comput. Geom.},
volume = {18},
number = {4},
pages = {369--376},
year = {1997},
url = {https://doi.org/10.1007/PL00009322},
doi = {10.1007/PL00009322},
timestamp = {Fri, 25 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/LovaszPS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/PachSS96,
author = {J{\'{a}}nos Pach and
Farhad Shahrokhi and
Mario Szegedy},
title = {Applications of the Crossing Number},
journal = {Algorithmica},
volume = {16},
number = {1},
pages = {111--117},
year = {1996},
url = {https://doi.org/10.1007/BF02086610},
doi = {10.1007/BF02086610},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/PachSS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/FeigeGLSS96,
author = {Uriel Feige and
Shafi Goldwasser and
L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and
Shmuel Safra and
Mario Szegedy},
title = {Interactive Proofs and the Hardness of Approximating Cliques},
journal = {J. {ACM}},
volume = {43},
number = {2},
pages = {268--292},
year = {1996},
url = {https://doi.org/10.1145/226643.226652},
doi = {10.1145/226643.226652},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/FeigeGLSS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AlonMS96,
author = {Noga Alon and
Yossi Matias and
Mario Szegedy},
editor = {Gary L. Miller},
title = {The Space Complexity of Approximating the Frequency Moments},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory
of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996},
pages = {20--29},
publisher = {{ACM}},
year = {1996},
url = {https://doi.org/10.1145/237814.237823},
doi = {10.1145/237814.237823},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AlonMS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/NewmanS96,
author = {Ilan Newman and
Mario Szegedy},
editor = {Gary L. Miller},
title = {Public vs. Private Coin Flips in One Round Communication Games (Extended
Abstract)},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory
of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996},
pages = {561--570},
publisher = {{ACM}},
year = {1996},
url = {https://doi.org/10.1145/237814.238004},
doi = {10.1145/237814.238004},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/NewmanS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GalS95,
author = {Anna G{\'{a}}l and
Mario Szegedy},
title = {Fault Tolerant Circuits and Probabilistically Checkable Proofs},
booktitle = {Proceedings of the Tenth Annual Structure in Complexity Theory Conference,
Minneapolis, Minnesota, USA, June 19-22, 1995},
pages = {65--73},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/SCT.1995.514728},
doi = {10.1109/SCT.1995.514728},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/GalS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/compgeom/LovaszPS95,
author = {L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and
J{\'{a}}nos Pach and
Mario Szegedy},
editor = {Jack Snoeyink},
title = {On Conway's Thrackle Conjecture},
booktitle = {Proceedings of the Eleventh Annual Symposium on Computational Geometry,
Vancouver, B.C., Canada, June 5-12, 1995},
pages = {147--151},
publisher = {{ACM}},
year = {1995},
url = {https://doi.org/10.1145/220279.220295},
doi = {10.1145/220279.220295},
timestamp = {Mon, 14 Jun 2021 16:25:05 +0200},
biburl = {https://dblp.org/rec/conf/compgeom/LovaszPS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/NisanS94,
author = {Noam Nisan and
Mario Szegedy},
title = {On the Degree of Boolean Functions as Real Polynomials},
journal = {Comput. Complex.},
volume = {4},
pages = {301--313},
year = {1994},
url = {https://doi.org/10.1007/BF01263419},
doi = {10.1007/BF01263419},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/NisanS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/HalldorssonS94,
author = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Mario Szegedy},
title = {Lower Bounds for On-Line Graph Coloring},
journal = {Theor. Comput. Sci.},
volume = {130},
number = {1},
pages = {163--174},
year = {1994},
url = {https://doi.org/10.1016/0304-3975(94)90157-0},
doi = {10.1016/0304-3975(94)90157-0},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/HalldorssonS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/compgeom/PachSS94,
author = {J{\'{a}}nos Pach and
Farhad Shahrokhi and
Mario Szegedy},
editor = {Kurt Mehlhorn},
title = {Applications of the Crossing Number},
booktitle = {Proceedings of the Tenth Annual Symposium on Computational Geometry,
Stony Brook, New York, USA, June 6-8, 1994},
pages = {198--202},
publisher = {{ACM}},
year = {1994},
url = {https://doi.org/10.1145/177424.177629},
doi = {10.1145/177424.177629},
timestamp = {Mon, 14 Jun 2021 16:25:06 +0200},
biburl = {https://dblp.org/rec/conf/compgeom/PachSS94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Szegedy94,
author = {Mario Szegedy},
title = {A note on the Theta number of Lov{\'{a}}sz and the generalized
Delsarte bound},
booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
New Mexico, USA, 20-22 November 1994},
pages = {36--39},
publisher = {{IEEE} Computer Society},
year = {1994},
url = {https://doi.org/10.1109/SFCS.1994.365707},
doi = {10.1109/SFCS.1994.365707},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Szegedy94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/HajnalMPST93,
author = {Andr{\'{a}}s Hajnal and
Wolfgang Maass and
Pavel Pudl{\'{a}}k and
Mario Szegedy and
Gy{\"{o}}rgy Tur{\'{a}}n},
title = {Threshold Circuits of Bounded Depth},
journal = {J. Comput. Syst. Sci.},
volume = {46},
number = {2},
pages = {129--154},
year = {1993},
url = {https://doi.org/10.1016/0022-0000(93)90001-D},
doi = {10.1016/0022-0000(93)90001-D},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/HajnalMPST93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Szegedy93,
author = {Mario Szegedy},
title = {Functions with Bounded Symmetric Communication Complexity, Programs
over Commutative Monoids, and {ACC}},
journal = {J. Comput. Syst. Sci.},
volume = {47},
number = {3},
pages = {405--423},
year = {1993},
url = {https://doi.org/10.1016/0022-0000(93)90039-Y},
doi = {10.1016/0022-0000(93)90039-Y},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Szegedy93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SzegedyV93,
author = {Mario Szegedy and
Sundar Vishwanathan},
editor = {S. Rao Kosaraju and
David S. Johnson and
Alok Aggarwal},
title = {Locality based graph coloring},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM} Symposium on Theory of
Computing, May 16-18, 1993, San Diego, CA, {USA}},
pages = {201--207},
publisher = {{ACM}},
year = {1993},
url = {https://doi.org/10.1145/167088.167156},
doi = {10.1145/167088.167156},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SzegedyV93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/HajnalS92,
author = {P{\'{e}}ter Hajnal and
Mario Szegedy},
title = {On packing bipartite graphs},
journal = {Comb.},
volume = {12},
number = {3},
pages = {295--301},
year = {1992},
url = {https://doi.org/10.1007/BF01285818},
doi = {10.1007/BF01285818},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/HajnalS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cpc/BabaiS92,
author = {L{\'{a}}szl{\'{o}} Babai and
Mario Szegedy},
title = {Local Expansion of Ssymmetrical Graphs},
journal = {Comb. Probab. Comput.},
volume = {1},
pages = {1--11},
year = {1992},
url = {https://doi.org/10.1017/S0963548300000031},
doi = {10.1017/S0963548300000031},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cpc/BabaiS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/FortnowS92,
author = {Lance Fortnow and
Mario Szegedy},
title = {On the Power of Two-Local Random Reductions},
journal = {Inf. Process. Lett.},
volume = {44},
number = {6},
pages = {303--306},
year = {1992},
url = {https://doi.org/10.1016/0020-0190(92)90104-4},
doi = {10.1016/0020-0190(92)90104-4},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/FortnowS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/BabaiNS92,
author = {L{\'{a}}szl{\'{o}} Babai and
Noam Nisan and
Mario Szegedy},
title = {Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space
Trade-Offs},
journal = {J. Comput. Syst. Sci.},
volume = {45},
number = {2},
pages = {204--232},
year = {1992},
url = {https://doi.org/10.1016/0022-0000(92)90047-M},
doi = {10.1016/0022-0000(92)90047-M},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/BabaiNS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AroraLMSS92,
author = {Sanjeev Arora and
Carsten Lund and
Rajeev Motwani and
Madhu Sudan and
Mario Szegedy},
title = {Proof Verification and Hardness of Approximation Problems},
booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh,
Pennsylvania, USA, 24-27 October 1992},
pages = {14--23},
publisher = {{IEEE} Computer Society},
year = {1992},
url = {https://doi.org/10.1109/SFCS.1992.267823},
doi = {10.1109/SFCS.1992.267823},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AroraLMSS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HalldorssonS92,
author = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Mario Szegedy},
editor = {Greg N. Frederickson},
title = {Lower Bounds for On-Line Graph Coloring},
booktitle = {Proceedings of the Third Annual {ACM/SIGACT-SIAM} Symposium on Discrete
Algorithms, 27-29 January 1992, Orlando, Florida, {USA}},
pages = {211--216},
publisher = {{ACM/SIAM}},
year = {1992},
url = {http://dl.acm.org/citation.cfm?id=139404.139452},
timestamp = {Thu, 05 Jul 2018 07:29:02 +0200},
biburl = {https://dblp.org/rec/conf/soda/HalldorssonS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/NisanS92,
author = {Noam Nisan and
Mario Szegedy},
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
title = {On the Degree of Boolean Functions as Real Polynomials},
booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
pages = {462--467},
publisher = {{ACM}},
year = {1992},
url = {https://doi.org/10.1145/129712.129757},
doi = {10.1145/129712.129757},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/NisanS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/SimonS92,
author = {Janos Simon and
Mario Szegedy},
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
title = {On the Complexity of {RAM} with Various Operation Sets},
booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
pages = {624--631},
publisher = {{ACM}},
year = {1992},
url = {https://doi.org/10.1145/129712.129773},
doi = {10.1145/129712.129773},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/SimonS92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/asiacrypt/FortnowS91,
author = {Lance Fortnow and
Mario Szegedy},
editor = {Hideki Imai and
Ronald L. Rivest and
Tsutomu Matsumoto},
title = {On the Power of Two-Local Random Reductions},
booktitle = {Advances in Cryptology - {ASIACRYPT} '91, International Conference
on the Theory and Applications of Cryptology, Fujiyoshida, Japan,
November 11-14, 1991, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {739},
pages = {346--351},
publisher = {Springer},
year = {1991},
url = {https://doi.org/10.1007/3-540-57332-1\_29},
doi = {10.1007/3-540-57332-1\_29},
timestamp = {Tue, 14 May 2019 10:00:40 +0200},
biburl = {https://dblp.org/rec/conf/asiacrypt/FortnowS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/HalldorssonS91,
author = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Mario Szegedy},
editor = {Lyle A. McGeoch and
Daniel Dominic Sleator},
title = {Lower Bounds for On-line Graph Coloring},
booktitle = {On-Line Algorithms, Proceedings of a {DIMACS} Workshop, New Brunswick,
New Jersey, USA, February 11-13, 1991},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {7},
pages = {169--179},
publisher = {{DIMACS/AMS}},
year = {1991},
url = {https://doi.org/10.1090/dimacs/007/15},
doi = {10.1090/DIMACS/007/15},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/HalldorssonS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/FeigeGLSS91,
author = {Uriel Feige and
Shafi Goldwasser and
L{\'{a}}szl{\'{o}} Lov{\'{a}}sz and
Shmuel Safra and
Mario Szegedy},
title = {Approximating Clique is Almost NP-Complete (Preliminary Version)},
booktitle = {32nd Annual Symposium on Foundations of Computer Science, San Juan,
Puerto Rico, 1-4 October 1991},
pages = {2--12},
publisher = {{IEEE} Computer Society},
year = {1991},
url = {https://doi.org/10.1109/SFCS.1991.185341},
doi = {10.1109/SFCS.1991.185341},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/FeigeGLSS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BabaiFLS91,
author = {L{\'{a}}szl{\'{o}} Babai and
Lance Fortnow and
Leonid A. Levin and
Mario Szegedy},
editor = {Cris Koutsougeras and
Jeffrey Scott Vitter},
title = {Checking Computations in Polylogarithmic Time},
booktitle = {Proceedings of the 23rd Annual {ACM} Symposium on Theory of Computing,
May 5-8, 1991, New Orleans, Louisiana, {USA}},
pages = {21--31},
publisher = {{ACM}},
year = {1991},
url = {https://doi.org/10.1145/103418.103428},
doi = {10.1145/103418.103428},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BabaiFLS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/SimonS90,
author = {Janos Simon and
Mario Szegedy},
editor = {Jin{-}Yi Cai},
title = {A New Lower Bound Theorem for Read-Only-Once Branching Programs and
its Applications},
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 = {183--193},
publisher = {{DIMACS/AMS}},
year = {1990},
url = {https://doi.org/10.1090/dimacs/013/11},
doi = {10.1090/DIMACS/013/11},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/SimonS90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Szegedy90,
author = {Mario Szegedy},
editor = {Harriet Ortiz},
title = {Functions with Bounded Symmetric Communication Complexity and Circuits
with {\textbackslash}mathop mod m Gates},
booktitle = {Proceedings of the 22nd Annual {ACM} Symposium on Theory of Computing,
May 13-17, 1990, Baltimore, Maryland, {USA}},
pages = {278--286},
publisher = {{ACM}},
year = {1990},
url = {https://doi.org/10.1145/100216.100252},
doi = {10.1145/100216.100252},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Szegedy90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BabaiNS89,
author = {L{\'{a}}szl{\'{o}} Babai and
Noam Nisan and
Mario Szegedy},
editor = {David S. Johnson},
title = {Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended
Abstract)},
booktitle = {Proceedings of the 21st Annual {ACM} Symposium on Theory of Computing,
May 14-17, 1989, Seattle, Washington, {USA}},
pages = {1--11},
publisher = {{ACM}},
year = {1989},
url = {https://doi.org/10.1145/73007.73008},
doi = {10.1145/73007.73008},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BabaiNS89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cacm/RubinsteinSS88,
author = {David Rubinstein and
Jeffrey O. Shallit and
Mario Szegedy},
title = {A Subset Coloring Algorithm and Its Applications to Computer Graphics},
journal = {Commun. {ACM}},
volume = {31},
number = {10},
pages = {1228--1232},
year = {1988},
url = {https://doi.org/10.1145/63039.63046},
doi = {10.1145/63039.63046},
timestamp = {Mon, 09 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cacm/RubinsteinSS88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HajnalMPST87,
author = {Andr{\'{a}}s Hajnal and
Wolfgang Maass and
Pavel Pudl{\'{a}}k and
Mario Szegedy and
Gy{\"{o}}rgy Tur{\'{a}}n},
title = {Threshold circuits of bounded depth},
booktitle = {28th Annual Symposium on Foundations of Computer Science, Los Angeles,
California, USA, 27-29 October 1987},
pages = {99--110},
publisher = {{IEEE} Computer Society},
year = {1987},
url = {https://doi.org/10.1109/SFCS.1987.59},
doi = {10.1109/SFCS.1987.59},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HajnalMPST87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/Szegedy86,
author = {Mario Szegedy},
title = {The solution of Graham's greatest common divisor problem},
journal = {Comb.},
volume = {6},
number = {1},
pages = {67--71},
year = {1986},
url = {https://doi.org/10.1007/BF02579410},
doi = {10.1007/BF02579410},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/Szegedy86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eik/BuroschGLS84,
author = {Gustav Burosch and
Waleri Wassiljewitsch Gorlow and
Roger Labahn and
Mario Szegedy},
title = {The Telephone Problem for Connected Graphs},
journal = {J. Inf. Process. Cybern.},
volume = {20},
number = {10/11},
pages = {557--573},
year = {1984},
timestamp = {Fri, 06 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eik/BuroschGLS84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
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 2024-04-16 22:59 CEST 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:
