Szegedy, Mario; Newman, Ilan; Lee, Troy Query complexity (to appear). (English) Zbl 07177078 Singapore: World Scientific (ISBN 978-981-322-320-2/hbk). 200 p. (2024). MSC: 68-02 68P05 68Q25 68R05 68W20 PDFBibTeX XMLCite \textit{M. Szegedy} et al., Query complexity (to appear). Singapore: World Scientific (2024; Zbl 07177078) Full Text: DOI
Szegedy, Mario; Yu, Jingjin An initial study of budgeted Steiner networks. (English) Zbl 07779752 CGT, Comput. Geom. Topol. 2, No. 2, Paper No. 4, 13 p. (2023). MSC: 68R10 90C35 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{J. Yu}, CGT, Comput. Geom. Topol. 2, No. 2, Paper No. 4, 13 p. (2023; Zbl 07779752) Full Text: DOI
Carqueville, Nils; Meir, Ehud; Szegedy, Lorant Invariants of r-spin TQFTs and non-semisimplicity. arXiv:2306.08608 Preprint, arXiv:2306.08608 [math.QA] (2023). MSC: 57K16 18M05 BibTeX Cite \textit{N. Carqueville} et al., ``Invariants of r-spin TQFTs and non-semisimplicity'', Preprint, arXiv:2306.08608 [math.QA] (2023) Full Text: arXiv OA License
Backhausz, Ágnes; Bordenave, Charles; Szegedy, Balázs Typicality and entropy of processes on infinite trees. (English. French summary) Zbl 1498.05192 Ann. Inst. Henri Poincaré, Probab. Stat. 58, No. 4, 1959-1980 (2022). MSC: 05C63 05C05 05C80 37A35 60F10 60C05 60G15 PDFBibTeX XMLCite \textit{Á. Backhausz} et al., Ann. Inst. Henri Poincaré, Probab. Stat. 58, No. 4, 1959--1980 (2022; Zbl 1498.05192) Full Text: DOI arXiv Link
Müller, Lukas; Szabo, Richard J.; Szegedy, Lóránt Symmetry defects and orbifolds of two-dimensional Yang-Mills theory. (English) Zbl 1490.81106 Lett. Math. Phys. 112, No. 2, Paper No. 18, 58 p. (2022). MSC: 81T13 PDFBibTeX XMLCite \textit{L. Müller} et al., Lett. Math. Phys. 112, No. 2, Paper No. 18, 58 p. (2022; Zbl 1490.81106) Full Text: DOI arXiv
Backhausz, Ágnes; Szegedy, Balázs Action convergence of operators and graphs. (English) Zbl 1482.05187 Can. J. Math. 74, No. 1, 72-121 (2022). MSC: 05C50 15B52 PDFBibTeX XMLCite \textit{Á. Backhausz} and \textit{B. Szegedy}, Can. J. Math. 74, No. 1, 72--121 (2022; Zbl 1482.05187) Full Text: DOI arXiv
Runkel, Ingo; Szegedy, Lóránt; Watts, Gérard M. T. Parity and Spin CFT with boundaries and defects. arXiv:2210.01057 Preprint, arXiv:2210.01057 [hep-th] (2022). BibTeX Cite \textit{I. Runkel} et al., ``Parity and Spin CFT with boundaries and defects'', Preprint, arXiv:2210.01057 [hep-th] (2022) Full Text: DOI arXiv OA License
Movassagh, Ramis; Szegedy, Mario; Wang, Guanyang Repeated Averages on Graphs. arXiv:2205.04535 Preprint, arXiv:2205.04535 [math.PR] (2022). BibTeX Cite \textit{R. Movassagh} et al., ``Repeated Averages on Graphs'', Preprint, arXiv:2205.04535 [math.PR] (2022) Full Text: arXiv OA License
Szegedy, Mario; Yu, Jingjin Budgeted Steiner Networks: Three Terminals with Equal Path Weights. arXiv:2201.11602 Preprint, arXiv:2201.11602 [cs.CG] (2022). BibTeX Cite \textit{M. Szegedy} and \textit{J. Yu}, ``Budgeted Steiner Networks: Three Terminals with Equal Path Weights'', Preprint, arXiv:2201.11602 [cs.CG] (2022) Full Text: arXiv OA License
Rabe, Markus N.; Szegedy, Christian Towards the automatic mathematician. (English) Zbl 1510.68116 Platzer, André (ed.) et al., Automated deduction – CADE 28. 28th international conference on automated deduction, virtual event, July 12–15, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12699, 25-37 (2021). Reviewer: Truong Hoang Le (Hà Nội) MSC: 68V15 68T05 68T50 68V20 PDFBibTeX XMLCite \textit{M. N. Rabe} and \textit{C. Szegedy}, Lect. Notes Comput. Sci. 12699, 25--37 (2021; Zbl 1510.68116) Full Text: DOI
Szegedy, Mario; Yu, Jingjin On rearrangement of items stored in stacks. (English) Zbl 1469.68137 Lavalle, Steven M. (ed.) et al., Algorithmic foundations of robotics XIV. Proceedings of the fourteenth workshop on the algorithmic foundations of robotics. Cham: Springer. Springer Proc. Adv. Robot. 17, 518-533 (2021). MSC: 68T40 68T20 90C27 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{J. Yu}, Springer Proc. Adv. Robot. 17, 518--533 (2021; Zbl 1469.68137) Full Text: DOI arXiv
Huang, Cupjin; Newman, Michael; Szegedy, Mario Explicit lower bounds on strong quantum simulation. (English) Zbl 1448.68243 IEEE Trans. Inf. Theory 66, No. 9, 5585-5600 (2020). MSC: 68Q12 68Q17 PDFBibTeX XMLCite \textit{C. Huang} et al., IEEE Trans. Inf. Theory 66, No. 9, 5585--5600 (2020; Zbl 1448.68243) Full Text: DOI arXiv
Bannink, Tom; Buhrman, Harry; Gilyén, András; Szegedy, Mario The interaction light cone of the discrete Bak-Sneppen, contact and other local processes. (English) Zbl 1480.60001 J. Stat. Phys. 176, No. 6, 1500-1525 (2019). MSC: 60-08 60G99 60J10 60J22 PDFBibTeX XMLCite \textit{T. Bannink} et al., J. Stat. Phys. 176, No. 6, 1500--1525 (2019; Zbl 1480.60001) Full Text: DOI arXiv
Backhausz, Ágnes; Szegedy, Balázs On the almost eigenvectors of random regular graphs. (English) Zbl 1414.05259 Ann. Probab. 47, No. 3, 1677-1725 (2019). MSC: 05C80 60B20 15B52 PDFBibTeX XMLCite \textit{Á. Backhausz} and \textit{B. Szegedy}, Ann. Probab. 47, No. 3, 1677--1725 (2019; Zbl 1414.05259) Full Text: DOI arXiv Euclid
Szegedy, Mario What do QAOA energies reveal about graphs? arXiv:1912.12277 Preprint, arXiv:1912.12277 [quant-ph] (2019). BibTeX Cite \textit{M. Szegedy}, ``What do QAOA energies reveal about graphs?'', Preprint, arXiv:1912.12277 [quant-ph] (2019) Full Text: arXiv OA License
Backhausz, Ágnes; Szegedy, Balázs On large-girth regular graphs and random processes on trees. (English) Zbl 1401.05267 Random Struct. Algorithms 53, No. 3, 389-416 (2018). MSC: 05C80 PDFBibTeX XMLCite \textit{Á. Backhausz} and \textit{B. Szegedy}, Random Struct. Algorithms 53, No. 3, 389--416 (2018; Zbl 1401.05267) Full Text: DOI arXiv Link
Catarata, Jan Dean; Corbett, Scott; Stern, Harry; Szegedy, Mario; Vyskocil, Tomas; Zhang, Zheng The Moser-Tardos resample algorithm: where is the limit? (An experimental inquiry). (English) Zbl 1430.68466 Fekete, Sándor (ed.) et al., Proceedings of the 19th workshop on algorithm engineering and experiments, ALENEX ’17, Barcelona, Spain, January 17–18, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 159-171 (2017). MSC: 68W40 60C05 68R05 68Q87 PDFBibTeX XMLCite \textit{J. D. Catarata} et al., in: Proceedings of the 19th workshop on algorithm engineering and experiments, ALENEX '17, Barcelona, Spain, January 17--18, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 159--171 (2017; Zbl 1430.68466) Full Text: DOI
Loos, Sarah; Irving, Geoffrey; Szegedy, Christian; Kaliszyk, Cezary Deep network guided proof search. (English) Zbl 1403.68197 Eiter, Thomas (ed.) et al., LPAR-21. 21st international conference on logic for programming, artificial intelligence and reasoning, Maun, Botswana, May 8–12, 2017. Selected papers. Manchester: EasyChair. EPiC Series in Computing 46, 85-105 (2017). MSC: 68T05 68T15 PDFBibTeX XMLCite \textit{S. Loos} et al., EPiC Ser. Comput. 46, 85--105 (2017; Zbl 1403.68197) Full Text: DOI arXiv
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario Streaming algorithms for independent sets in sparse hypergraphs. (English) Zbl 1347.68363 Algorithmica 76, No. 2, 490-501 (2016). MSC: 68W20 05C65 05C69 05C85 68W27 PDFBibTeX XMLCite \textit{B. V. Halldórsson} et al., Algorithmica 76, No. 2, 490--501 (2016; Zbl 1347.68363) Full Text: DOI
Kun, Gábor; Szegedy, Mario A new line of attack on the dichotomy conjecture. (English) Zbl 1327.05183 Eur. J. Comb. 52, Part B, 338-367 (2016). MSC: 05C40 68Q17 PDFBibTeX XMLCite \textit{G. Kun} and \textit{M. Szegedy}, Eur. J. Comb. 52, Part B, 338--367 (2016; Zbl 1327.05183) Full Text: DOI
Backhausz, Ágnes; Szegedy, Balázs; Virág, Bálint Ramanujan graphings and correlation decay in local algorithms. (English) Zbl 1325.05159 Random Struct. Algorithms 47, No. 3, 424-435 (2015). MSC: 05C85 68W20 PDFBibTeX XMLCite \textit{Á. Backhausz} et al., Random Struct. Algorithms 47, No. 3, 424--435 (2015; Zbl 1325.05159) Full Text: DOI arXiv
Szegedy, Mario; Xu, Yixin Impossibility Theorems and the Universal Algebraic Toolkit. arXiv:1506.01315 Preprint, arXiv:1506.01315 [cs.CC] (2015). BibTeX Cite \textit{M. Szegedy} and \textit{Y. Xu}, ``Impossibility Theorems and the Universal Algebraic Toolkit'', Preprint, arXiv:1506.01315 [cs.CC] (2015) Full Text: arXiv OA License
Chiu, Well Y.; Szegedy, Mario; Wang, Chengu; Xu, Yixin The garden hose complexity for the equality function. (English) Zbl 1445.68101 Gu, Qianping (ed.) et al., Algorithmic aspects in information and management. 10th international conference, AAIM 2014, Vancouver, BC, Canada, July 8–11, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8546, 112-123 (2014). MSC: 68Q11 20B99 81P94 PDFBibTeX XMLCite \textit{W. Y. Chiu} et al., Lect. Notes Comput. Sci. 8546, 112--123 (2014; Zbl 1445.68101) Full Text: DOI arXiv
Srivastava, Piyush; Szegedy, Mario A simplified proof of a Lee-Yang type theorem. arXiv:1407.5991 Preprint, arXiv:1407.5991 [math-ph] (2014). BibTeX Cite \textit{P. Srivastava} and \textit{M. Szegedy}, ``A simplified proof of a Lee-Yang type theorem'', Preprint, arXiv:1407.5991 [math-ph] (2014) Full Text: arXiv OA License
Kiltz, Eike; Pietrzak, Krzysztof; Szegedy, Mario Digital signatures with minimal overhead from indifferentiable random invertible functions. (English) Zbl 1310.94156 Canetti, Ran (ed.) et al., Advances in cryptology – CRYPTO 2013. 33rd annual cryptology conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-40040-7/pbk). Lecture Notes in Computer Science 8042, 571-588 (2013). MSC: 94A60 PDFBibTeX XMLCite \textit{E. Kiltz} et al., Lect. Notes Comput. Sci. 8042, 571--588 (2013; Zbl 1310.94156) Full Text: DOI
Szegedy, Mario The Lovász local lemma – a survey. (English) Zbl 1381.05083 Bulatov, Andrei A. (ed.) et al., Computer science – theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38535-3/pbk). Lecture Notes in Computer Science 7913, 1-11 (2013). MSC: 05D40 60C05 PDFBibTeX XMLCite \textit{M. Szegedy}, Lect. Notes Comput. Sci. 7913, 1--11 (2013; Zbl 1381.05083) Full Text: DOI
Halldórsson, Magnús M.; Sun, Xiaoming; Szegedy, Mario; Wang, Chengu Streaming and communication complexity of clique approximation. (English) Zbl 1272.68333 Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 449-460 (2012). MSC: 68R10 05C69 68Q17 68Q25 68W20 PDFBibTeX XMLCite \textit{M. M. Halldórsson} et al., Lect. Notes Comput. Sci. 7391, 449--460 (2012; Zbl 1272.68333) Full Text: DOI
Kolipaka, Kashyap; Szegedy, Mario; Xu, Yixin A sharper local lemma with improved applications. (English) Zbl 1372.05230 Gupta, Anupam (ed.) et al., 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. Berlin: Springer (ISBN 978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 603-614 (2012). MSC: 05D40 05C15 60C05 PDFBibTeX XMLCite \textit{K. Kolipaka} et al., Lect. Notes Comput. Sci. 7408, 603--614 (2012; Zbl 1372.05230) Full Text: DOI
Lee, Troy; Mittal, Rajat; Reichardt, Ben W.; Špalek, Robert; Szegedy, Mario Quantum query complexity of state conversion. (English) Zbl 1292.68069 Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 344-353 (2011). MSC: 68Q12 81P68 PDFBibTeX XMLCite \textit{T. Lee} et al., in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science -- FOCS 2011, Palm Springs, CA, USA, October 22--25. Los Alamitos, CA: IEEE Computer Society. 344--353 (2011; Zbl 1292.68069) Full Text: DOI arXiv
Kolipaka, Kashyap Babu Rao; Szegedy, Mario Moser and Tardos meet Lovász. (English) Zbl 1288.68129 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 235-244 (2011). MSC: 68Q25 05C85 68R05 68R10 PDFBibTeX XMLCite \textit{K. B. R. Kolipaka} and \textit{M. Szegedy}, in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 235--244 (2011; Zbl 1288.68129) Full Text: DOI
Seress, Ákos (ed.); Szegedy, Mario (ed.) Combinatorics, groups, algorithms, and complexity: conference in honor of Laci Babai’s 60th birthday. (English) Zbl 1286.00059 Discrete Math. Theor. Comput. Sci. 13, No. 4, 1-4 (2011). MSC: 00B25 68-06 01A70 PDFBibTeX XMLCite \textit{Á. Seress} (ed.) and \textit{M. Szegedy} (ed.), Discrete Math. Theor. Comput. Sci. 13, No. 4, 1--4 (2011; Zbl 1286.00059) Full Text: Link
Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Losievskaja, Elena; Szegedy, Mario Streaming algorithms for independent sets. (English) Zbl 1288.68189 Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 641-652 (2010). MSC: 68R10 05C69 05C85 PDFBibTeX XMLCite \textit{B. V. Halldórsson} et al., Lect. Notes Comput. Sci. 6198, 641--652 (2010; Zbl 1288.68189) Full Text: DOI
Kun, Gábor; Szegedy, Mario A new line of attack on the dichotomy conjecture. (English) Zbl 1304.68076 Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 725-734 (2009). MSC: 68Q25 08A40 68Q17 PDFBibTeX XMLCite \textit{G. Kun} and \textit{M. Szegedy}, in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC '09. Bethesda, MD, USA, May 31 -- June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 725--734 (2009; Zbl 1304.68076) Full Text: DOI Link
Santha, Miklos; Szegedy, Mario Quantum and classical query complexities of local search are polynomially related. (English) Zbl 1191.68310 Algorithmica 55, No. 3, 557-575 (2009). MSC: 68Q05 68Q10 68Q25 81P68 PDFBibTeX XMLCite \textit{M. Santha} and \textit{M. Szegedy}, Algorithmica 55, No. 3, 557--575 (2009; Zbl 1191.68310) Full Text: DOI
Mukkamala, Padmini; Szegedy, Mario Geometric representation of cubic graphs with four directions. (English) Zbl 1200.05149 Comput. Geom. 42, No. 9, 842-851 (2009). MSC: 05C62 PDFBibTeX XMLCite \textit{P. Mukkamala} and \textit{M. Szegedy}, Comput. Geom. 42, No. 9, 842--851 (2009; Zbl 1200.05149) Full Text: DOI
Roland, Jérémie; Szegedy, Mario Amortized communication complexity of distributions. (English) Zbl 1248.68261 Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 738-749 (2009). MSC: 68Q25 68M12 PDFBibTeX XMLCite \textit{J. Roland} and \textit{M. Szegedy}, Lect. Notes Comput. Sci. 5555, 738--749 (2009; Zbl 1248.68261) Full Text: DOI Link
Chen, Xiaomin; Pach, János; Szegedy, Mario; Tardos, Gábor Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. (English) Zbl 1228.05226 Random Struct. Algorithms 34, No. 1, 11-23 (2009). MSC: 05C69 52B55 05C15 68R10 68U05 PDFBibTeX XMLCite \textit{X. Chen} et al., Random Struct. Algorithms 34, No. 1, 11--23 (2009; Zbl 1228.05226) Full Text: DOI Link
Chen, Xiaomin; Pach, János; Szegedy, Mario; Tardos, Gábor Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. (English) Zbl 1192.05099 Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 94-101 (2008). MSC: 05C62 05C15 52C10 68U05 68W40 PDFBibTeX XMLCite \textit{X. Chen} et al., in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 94--101 (2008; Zbl 1192.05099)
Azimian, Kooshiar; Szegedy, Mario Parallel repetition of the odd cycle game. (English) Zbl 1136.68407 Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 676-686 (2008). MSC: 68Q25 03F20 91A05 91A80 PDFBibTeX XMLCite \textit{K. Azimian} and \textit{M. Szegedy}, Lect. Notes Comput. Sci. 4957, 676--686 (2008; Zbl 1136.68407) Full Text: DOI
Szegedy, Mario; Thorup, Mikkel On the variance of subset sum estimation. (English) Zbl 1151.68395 Arge, Lars (ed.) et al., Algorithms – ESA 2007. 15th annual European symposium, Eilat, Israel, October 8–10, 2007, Proceedings. Berlin: Springer (ISBN 978-3-540-75519-7/pbk). Lecture Notes in Computer Science 4698, 75-86 (2007). MSC: 68P15 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{M. Thorup}, Lect. Notes Comput. Sci. 4698, 75--86 (2007; Zbl 1151.68395) Full Text: DOI
Magniez, Frédéric; Santha, Miklos; Szegedy, Mario Quantum algorithms for the triangle problem. (English) Zbl 1166.68032 SIAM J. Comput. 37, No. 2, 413-424 (2007). Reviewer: Francesco Scarcello (Rende) MSC: 68R10 05C85 68Q25 81P68 PDFBibTeX XMLCite \textit{F. Magniez} et al., SIAM J. Comput. 37, No. 2, 413--424 (2007; Zbl 1166.68032) Full Text: DOI arXiv
Mittal, Rajat; Szegedy, Mario Product rules in semidefinite programming. (English) Zbl 1135.90378 Csuhaj-Varjú, Erzsébet (ed.) et al., Fundamentals of computation theory. 16th international symposium, FCT 2007, Budapest, Hungary, August 27–30, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74239-5/pbk). Lecture Notes in Computer Science 4639, 435-445 (2007). MSC: 90C22 90C27 90C35 81P68 91A80 PDFBibTeX XMLCite \textit{R. Mittal} and \textit{M. Szegedy}, Lect. Notes Comput. Sci. 4639, 435--445 (2007; Zbl 1135.90378) Full Text: DOI
Chattopadhyay, Arkadev; Krebs, Andreas; Koucký, Michal; Szegedy, Mario; Tesson, Pascal; Thérien, Denis Languages with bounded multiparty communication complexity. (English) Zbl 1186.68249 Thomas, Wolfgang (ed.) et al., STACS 2007. 24th annual symposium on theoretical aspects of computer science, Aachen, Germany, February 22–24, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-70917-6/pbk). Lecture Notes in Computer Science 4393, 500-511 (2007). MSC: 68Q45 68Q25 PDFBibTeX XMLCite \textit{A. Chattopadhyay} et al., Lect. Notes Comput. Sci. 4393, 500--511 (2007; Zbl 1186.68249) Full Text: DOI
Szegedy, Mario The DLT priority sampling is essentially optimal. (English) Zbl 1301.68166 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 150-158 (2006). MSC: 68Q25 68M10 68M11 68Q87 PDFBibTeX XMLCite \textit{M. Szegedy}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 150--158 (2006; Zbl 1301.68166) Full Text: DOI
Špalek, Robert; Szegedy, Mario All quantum adversary methods are equivalent. (English) Zbl 1213.68289 Theory Comput. 2, Paper No. 1, 1-18 (2006). MSC: 68Q12 68Q17 PDFBibTeX XMLCite \textit{R. Špalek} and \textit{M. Szegedy}, Theory Comput. 2, Paper No. 1, 1--18 (2006; Zbl 1213.68289) Full Text: DOI arXiv
Laplante, Sophie; Lee, Troy; Szegedy, Mario The quantum adversary method and classical formula size power bounds. (English) Zbl 1132.68032 Comput. Complexity 15, No. 2, 163-196 (2006). MSC: 68Q17 68Q30 81P68 PDFBibTeX XMLCite \textit{S. Laplante} et al., Comput. Complexity 15, No. 2, 163--196 (2006; Zbl 1132.68032) Full Text: DOI arXiv
Chen, Su; Imielinski, Tomasz; Johnsgard, Karin; Smith, Donald; Szegedy, Mario A dichotomy theorem for typed constraint satisfaction problems. (English) Zbl 1187.68257 Biere, Armin (ed.) et al., Theory and applications of satisfiability testing – SAT 2006. 9th international conference, Seattle, WA, USA, August 12–15, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37206-7/pbk). Lecture Notes in Computer Science 4121, 226-239 (2006). MSC: 68Q25 68T20 PDFBibTeX XMLCite \textit{S. Chen} et al., Lect. Notes Comput. Sci. 4121, 226--239 (2006; Zbl 1187.68257) Full Text: DOI
Magniez, Frédéric; Santha, Miklos; Szegedy, Mario Quantum algorithms for the triangle problem. (English) Zbl 1297.68078 Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 1109-1117 (2005). MSC: 68Q12 05C85 PDFBibTeX XMLCite \textit{F. Magniez} et al., in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 1109--1117 (2005; Zbl 1297.68078)
Chen, Xiaomin; Szegedy, Mario; Wang, Lei Optimally balanced forward degree sequence. (English) Zbl 1128.05302 Wang, Lusheng (ed.), Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28061-8/pbk). Lecture Notes in Computer Science 3595, 680-689 (2005). MSC: 05C07 PDFBibTeX XMLCite \textit{X. Chen} et al., Lect. Notes Comput. Sci. 3595, 680--689 (2005; Zbl 1128.05302) Full Text: DOI
Špalek, Robert; Szegedy, Mario All quantum adversary methods are equivalent. (English) Zbl 1081.68025 Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 1299-1311 (2005). MSC: 68Q17 81P68 PDFBibTeX XMLCite \textit{R. Špalek} and \textit{M. Szegedy}, Lect. Notes Comput. Sci. 3580, 1299--1311 (2005; Zbl 1081.68025) Full Text: DOI
Szegedy, Mario Probabilistic verification and non-approximability. (English) Zbl 1274.90394 Du, Ding-Zhu (ed.) et al., Handbook of combinatorial optimization. Supplement Volume B. New York, NY: Springer (ISBN 0-387-23829-8/hbk). 83-191 (2005). MSC: 90C30 PDFBibTeX XMLCite \textit{M. Szegedy}, in: Handbook of combinatorial optimization. Supplement Volume B. New York, NY: Springer. 83--191 (2005; Zbl 1274.90394) Full Text: DOI
Santha, Miklos; Szegedy, Mario Quantum and classical query complexities of local search are polynomially related. (English) Zbl 1192.68266 Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 494-501, electronic only (2004). MSC: 68Q05 68Q10 68Q25 81P68 PDFBibTeX XMLCite \textit{M. Santha} and \textit{M. Szegedy}, in: Proceedings of the 36th annual ACM symposium on theory of computing, STOC 2004. Chicago, IL, USA, June 13--15, 2004. New York, NY: ACM Press. 494--501 (2004; Zbl 1192.68266) Full Text: DOI
Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario Long monotone paths in line arrangements. (English) Zbl 1065.52016 Discrete Comput. Geom. 32, No. 2, 167-176 (2004). Reviewer: Stefan Nickel (Saarbrücken) MSC: 52C30 52C35 68U05 PDFBibTeX XMLCite \textit{J. Balogh} et al., Discrete Comput. Geom. 32, No. 2, 167--176 (2004; Zbl 1065.52016) Full Text: DOI
Szegedy, Mario; Chen, Xiaomin Computing Boolean functions from multiple faulty copies of input bits. (English) Zbl 1047.94022 Theor. Comput. Sci. 321, No. 1, 149-170 (2004). MSC: 94C10 90C05 06E30 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{X. Chen}, Theor. Comput. Sci. 321, No. 1, 149--170 (2004; Zbl 1047.94022) Full Text: DOI
Balogh, Jazsef; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario Long monotone paths in line arrangements. (English) Zbl 1376.52040 Proceedings of the 19th annual symposium on computational geometry, SCG/SoCG 2003, San Diego, CA, USA, June 8–10, 2003. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-663-3). 124-128 (2003). MSC: 52C30 52C35 68U05 PDFBibTeX XMLCite \textit{J. Balogh} et al., in: Proceedings of the 19th annual symposium on computational geometry, SCG/SoCG 2003, San Diego, CA, USA, June 8--10, 2003. New York, NY: Association for Computing Machinery (ACM). 124--128 (2003; Zbl 1376.52040) Full Text: DOI
Pach, János; Szegedy, Mario The number of simplices embracing the origin. (English) Zbl 1080.52502 Bezdek, András (ed.), Discrete geometry. In honor of W. Kuperberg’s 60th birthday. New York, NY: Marcel Dekker (ISBN 0-8247-0968-3/hbk). Pure Appl. Math., Marcel Dekker 253, 381-386 (2003). MSC: 52A22 PDFBibTeX XMLCite \textit{J. Pach} and \textit{M. Szegedy}, Pure Appl. Math., Marcel Dekker 253, 381--386 (2003; Zbl 1080.52502)
Abért, Miklós; Nikolov, Nikolay; Szegedy, Balázs Congruence subgroup growth of arithmetic groups in positive characteristic. (English) Zbl 1036.20043 Duke Math. J. 117, No. 2, 367-383 (2003). Reviewer: L. N. Vaserstein (University Park) MSC: 20H05 20E07 20G30 17B45 20E18 PDFBibTeX XMLCite \textit{M. Abért} et al., Duke Math. J. 117, No. 2, 367--383 (2003; Zbl 1036.20043) Full Text: DOI
Szegedy, Mario; Chen, Xiaomin Computing Boolean functions from multiple faulty copies of input bits. (English) Zbl 1059.68575 Rajsbaum, Sergio (ed.), LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3–6, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43400-3). Lect. Notes Comput. Sci. 2286, 539-553 (2002). MSC: 68Q05 68Q17 68Q25 68R05 90C09 94C12 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{X. Chen}, Lect. Notes Comput. Sci. 2286, 539--553 (2002; Zbl 1059.68575) Full Text: Link
Alon, Noga; Gibbons, Phillip B.; Matias, Yossi; Szegedy, Mario Tracking join and self-join sizes in limited storage. (English) Zbl 1051.68136 J. Comput. Syst. Sci. 64, No. 3, 719-747 (2002). MSC: 68W05 PDFBibTeX XMLCite \textit{N. Alon} et al., J. Comput. Syst. Sci. 64, No. 3, 719--747 (2002; Zbl 1051.68136) Full Text: DOI
Alon, Noga; Fischer, Eldar; Szegedy, Mario Parent-identifying codes. (English) Zbl 0980.94039 J. Comb. Theory, Ser. A 95, No. 2, 349-359 (2001). MSC: 94B60 94B65 PDFBibTeX XMLCite \textit{N. Alon} et al., J. Comb. Theory, Ser. A 95, No. 2, 349--359 (2001; Zbl 0980.94039) Full Text: DOI
Alon, Noga; Krivelevich, Michael; Newman, Ilan; Szegedy, Mario Regular languages are testable with a constant number of queries. (English) Zbl 0992.68064 SIAM J. Comput. 30, No. 6, 1842-1862 (2001). MSC: 68Q25 68W20 68Q45 PDFBibTeX XMLCite \textit{N. Alon} et al., SIAM J. Comput. 30, No. 6, 1842--1862 (2001; Zbl 0992.68064) Full Text: DOI
Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario Efficient testing of large graphs. (English) Zbl 1052.68096 Combinatorica 20, No. 4, 451-476 (2000). Reviewer: Tomas Dvorak (Praha) MSC: 68R10 05C85 05C35 PDFBibTeX XMLCite \textit{N. Alon} et al., Combinatorica 20, No. 4, 451--476 (2000; Zbl 1052.68096) Full Text: DOI
Szegedy, Mario Many-valued logics and holographic proofs. (English) Zbl 0938.03022 Wiedermann, Jiří (ed.) et al., Automata, languages and programming. 26th international colloquium, ICALP ‘99. Prague, Czech Republic, July 11-15, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1644, 676-686 (1999). MSC: 03B35 03B50 68T15 68Q10 68Q25 PDFBibTeX XMLCite \textit{M. Szegedy}, Lect. Notes Comput. Sci. 1644, 676--686 (1999; Zbl 0938.03022)
Alon, Noga; Matias, Yossi; Szegedy, Mario The space complexity of approximating the frequency moments. (English) Zbl 0938.68153 J. Comput. Syst. Sci. 58, No. 1, 137-147 (1999). MSC: 68W20 68P99 68Q25 PDFBibTeX XMLCite \textit{N. Alon} et al., J. Comput. Syst. Sci. 58, No. 1, 137--147 (1999; Zbl 0938.68153) Full Text: DOI
Szegedy, Mario A clique size bounding technique with application to nonlinear codes. (English) Zbl 0948.94020 Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM. S 971-S 972 (1999). MSC: 94B60 05C69 94B65 PDFBibTeX XMLCite \textit{M. Szegedy}, in: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, SODA '99. Baltimore, MD, USA, January 17--19, 1999. Philadelphia, PA: SIAM. 971--972 (1999; Zbl 0948.94020)
Kaplan, Haim; Strauss, Martin; Szegedy, Mario Just the fax-differentiating voice and fax phone lines using call billing data. (English) Zbl 1012.68537 Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM. S 935-S 936 (1999). MSC: 68T10 PDFBibTeX XMLCite \textit{H. Kaplan} et al., in: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, SODA '99. Baltimore, MD, USA, January 17--19, 1999. Philadelphia, PA: SIAM. 935--936 (1999; Zbl 1012.68537)
Johnson, David S.; Szegedy, Mario What are the least tractable instances of max independent set? (English) Zbl 0929.68089 Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17–19, 1999. Philadelphia, PA: SIAM. S 927-S 928 (1999). MSC: 68R10 05C05 PDFBibTeX XMLCite \textit{D. S. Johnson} and \textit{M. Szegedy}, in: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, SODA '99. Baltimore, MD, USA, January 17--19, 1999. Philadelphia, PA: SIAM. 927--928 (1999; Zbl 0929.68089)
Kaplan, Haim; Szegedy, Mario On-line complexity of monotone set systems (extended abstract). (English) Zbl 0947.91018 Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM. 507-516 (1999). MSC: 91A99 68Q25 PDFBibTeX XMLCite \textit{H. Kaplan} and \textit{M. Szegedy}, in: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, SODA '99. Baltimore, MD, USA, January 17--19, 1999. Philadelphia, PA: SIAM. 507--516 (1999; Zbl 0947.91018)
Alon, Noga; Szegedy, Mario Large sets of nearly orthogonal vectors. (English) Zbl 0923.05006 Graphs Comb. 15, No. 1, 1-4 (1999). Reviewer: J.E.Graver (Syracuse) MSC: 05A18 PDFBibTeX XMLCite \textit{N. Alon} and \textit{M. Szegedy}, Graphs Comb. 15, No. 1, 1--4 (1999; Zbl 0923.05006)
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario Proof verification and the hardness of approximation problems. (English) Zbl 1065.68570 J. ACM 45, No. 3, 501-555 (1998). MSC: 68Q15 03B35 03D15 68Q25 PDFBibTeX XMLCite \textit{S. Arora} et al., J. ACM 45, No. 3, 501--555 (1998; Zbl 1065.68570) Full Text: DOI
Lovász, L.; Pach, J.; Szegedy, M. On Conway’s thrackle conjecture. (English) Zbl 0892.05017 Discrete Comput. Geom. 18, No. 4, 369-376 (1997). Reviewer: A.T.White (Kalamazoo) MSC: 05C10 PDFBibTeX XMLCite \textit{L. Lovász} et al., Discrete Comput. Geom. 18, No. 4, 369--376 (1997; Zbl 0892.05017) Full Text: DOI
Pach, J.; Shahrokhi, F.; Szegedy, M. Applications of the crossing number. (English) Zbl 0851.68088 Algorithmica 16, No. 1, 111-117 (1996). MSC: 68R10 PDFBibTeX XMLCite \textit{J. Pach} et al., Algorithmica 16, No. 1, 111--117 (1996; Zbl 0851.68088) Full Text: DOI
Newman, Ilan; Szegedy, Mario Public vs. private coin flips in one round communication games. (Extended abstract). (English) Zbl 0936.68050 Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22-24, 1996. New York, NY: ACM, 561-570 (1996). MSC: 68Q15 68R10 PDFBibTeX XMLCite \textit{I. Newman} and \textit{M. Szegedy}, in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 561--570 (1996; Zbl 0936.68050)
Alon, Noga; Matias, Yossi; Szegedy, Mario The space complexity of approximating the frequency moments. (English) Zbl 0922.68057 Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22–24, 1996. New York, NY: ACM, 20-29 (1996). MSC: 68Q25 68P99 68W20 PDFBibTeX XMLCite \textit{N. Alon} et al., in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 20--29 (1996; Zbl 0922.68057)
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario Interactive proofs and the hardness of approximating cliques. (English) Zbl 0882.68129 J. ACM 43, No. 2, 268-292 (1996). MSC: 68T15 68W10 PDFBibTeX XMLCite \textit{U. Feige} et al., J. ACM 43, No. 2, 268--292 (1996; Zbl 0882.68129) Full Text: DOI Link
Nisan, Noam; Szegedy, Mario On the degree of Boolean functions as real polynomials. (English) Zbl 0829.68047 Comput. Complexity 4, No. 4, 301-313 (1994). MSC: 68Q05 68Q99 PDFBibTeX XMLCite \textit{N. Nisan} and \textit{M. Szegedy}, Comput. Complexity 4, No. 4, 301--313 (1994; Zbl 0829.68047) Full Text: DOI
Halldórsson, Magnus M.; Szegedy, Mario Lower bounds for on-line graph coloring. (English) Zbl 0822.68081 Theor. Comput. Sci. 130, No. 1, 163-174 (1994). MSC: 68R10 68Q25 05C15 PDFBibTeX XMLCite \textit{M. M. Halldórsson} and \textit{M. Szegedy}, Theor. Comput. Sci. 130, No. 1, 163--174 (1994; Zbl 0822.68081) Full Text: DOI
Fortnow, Lance; Szegedy, Mario On the power of two-local random reductions. (English) Zbl 0823.68035 Imai, Hideki (ed.) et al., Advances in Cryptology - ASIACRYPT ’91. International conference on the theory and application of cryptology, Fujiyoshida, Japan, November 11-14, 1991. Proceedings. Berlin: Springer- Verlag. Lect. Notes Comput. Sci. 739, 346-351 (1993). MSC: 68P25 94A60 PDFBibTeX XMLCite \textit{L. Fortnow} and \textit{M. Szegedy}, Lect. Notes Comput. Sci. 739, 346--351 (1993; Zbl 0823.68035)
Szegedy, Márió; Vishwanathan, Sundar Locality based graph coloring. (English) Zbl 1310.05099 Proceedings of the 25th annual ACM symposium on theory of computing, STOC ’93. San Diego, CA, USA, May 16–18, 1993. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-591-7). 201-207 (1993). MSC: 05C15 05C85 68Q17 68Q25 68W40 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{S. Vishwanathan}, in: Proceedings of the 25th annual ACM symposium on theory of computing, STOC '93. San Diego, CA, USA, May 16--18, 1993. New York, NY: Association for Computing Machinery (ACM). 201--207 (1993; Zbl 1310.05099) Full Text: DOI
Simon, Janos; Szegedy, Mario A new lower bound theorem for read-only-once branching programs and its applications. (English) Zbl 0801.68077 Cai, Jin-Yi (ed.), Advances in computational complexity theory. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 13, 183-193 (1993). MSC: 68Q25 PDFBibTeX XMLCite \textit{J. Simon} and \textit{M. Szegedy}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 13, 183--193 (1993; Zbl 0801.68077)
Szegedy, Mario Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC. (English) Zbl 0795.68107 J. Comput. Syst. Sci. 47, No. 3, 405-423 (1993). MSC: 68Q30 68Q25 94C10 20M35 PDFBibTeX XMLCite \textit{M. Szegedy}, J. Comput. Syst. Sci. 47, No. 3, 405--423 (1993; Zbl 0795.68107) Full Text: DOI
Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György Threshold circuits of bounded depth. (English) Zbl 0801.68052 J. Comput. Syst. Sci. 46, No. 2, 129-145 (1993). MSC: 68Q05 68Q10 PDFBibTeX XMLCite \textit{A. Hajnal} et al., J. Comput. Syst. Sci. 46, No. 2, 129--145 (1993; Zbl 0801.68052) Full Text: DOI
Babai, László; Nisan, Noam; Szegedy, Márió Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs. (English) Zbl 0769.68040 J. Comput. Syst. Sci. 45, No. 2, 204-232 (1992). MSC: 68Q25 PDFBibTeX XMLCite \textit{L. Babai} et al., J. Comput. Syst. Sci. 45, No. 2, 204--232 (1992; Zbl 0769.68040) Full Text: DOI
Hajnal, Péter; Szegedy, Márió On packing bipartite graphs. (English) Zbl 0772.05079 Combinatorica 12, No. 3, 295-301 (1992). Reviewer: W.K.Chen (Chicago) MSC: 05C70 05B40 PDFBibTeX XMLCite \textit{P. Hajnal} and \textit{M. Szegedy}, Combinatorica 12, No. 3, 295--301 (1992; Zbl 0772.05079) Full Text: DOI
Halldórsson, Magnús M.; Szegedy, Márió Lower bounds for on-line graph coloring. (English) Zbl 0829.68096 Frederickson, Greg (ed.), Proceedings of the third annual ACM-SIAM symposium on discrete algorithms, held January 27-29, 1992, in Orlando, FL, USA. Philadelphia, PA: SIAM. 211-216 (1992). MSC: 68R10 05C15 68Q25 05C85 PDFBibTeX XMLCite \textit{M. M. Halldórsson} and \textit{M. Szegedy}, in: Proceedings of the third annual ACM-SIAM symposium on discrete algorithms, SODA '92, held January 27--29, 1992, in Orlando, FL, USA. Philadelphia, PA: SIAM; New York, NY: ACM. 211--216 (1992; Zbl 0829.68096)
Halldórsson, Magnús M.; Szegedy, Márió Lower bounds for on-line graph coloring. (English) Zbl 0751.05040 On-line algorithms, Proc. DIMACS Workshop, New Brunswick/NJ (USA) 1991, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 7, 169-179 (1992). Reviewer: M.Kubale (Gdańsk) MSC: 05C15 68R10 68Q25 05C85 PDFBibTeX XMLCite \textit{M. M. Halldórsson} and \textit{M. Szegedy}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 7, 169--179 (1992; Zbl 0751.05040)
Babai, László; Szegedy, Mario Local expansion of symmetrical graphs. (English) Zbl 0792.05064 Comb. Probab. Comput. 1, No. 1, 1-11 (1992). MSC: 05C25 05C99 PDFBibTeX XMLCite \textit{L. Babai} and \textit{M. Szegedy}, Comb. Probab. Comput. 1, No. 1, 1--11 (1992; Zbl 0792.05064) Full Text: DOI
Fortnow, Lance; Szegedy, Mario On the power of two-local random reductions. (English) Zbl 0795.68076 Inf. Process. Lett. 44, No. 6, 303-306 (1992). MSC: 68Q15 68Q25 94C10 PDFBibTeX XMLCite \textit{L. Fortnow} and \textit{M. Szegedy}, Inf. Process. Lett. 44, No. 6, 303--306 (1992; Zbl 0795.68076) Full Text: DOI
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario Proof verification and hardness of approximation problems. (English) Zbl 0977.68539 33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24-27, 1992. Washington, DC: IEEE Computer Society Press, 14-23 (1992). MSC: 68Q15 68N15 PDFBibTeX XMLCite \textit{S. Arora} et al., in: 33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24--27, 1992. Washington, DC: IEEE Computer Society Press. 14--23 (1992; Zbl 0977.68539)
Szegedy, Mário; Tardos, Gábor On the decomposition of infinite series into monotone decreasing parts. (English) Zbl 0681.40004 Stud. Sci. Math. Hung. 23, No. 1-2, 81-83 (1988). Reviewer: G.Georganopoulos MSC: 40A05 PDFBibTeX XMLCite \textit{M. Szegedy} and \textit{G. Tardos}, Stud. Sci. Math. Hung. 23, No. 1--2, 81--83 (1988; Zbl 0681.40004)
Erdős, Paul; Pálfy, Péter Pál; Szegedy, M. \(a\pmod p\leq b\pmod p\) for all primes \(p\) implies \(a=b\). (English) Zbl 0616.10003 Am. Math. Mon. 94, 169-170 (1987). Reviewer: P. Erdős (Budapest) MSC: 11A05 11A07 PDFBibTeX XMLCite \textit{P. Erdős} et al., Am. Math. Mon. 94, 169--170 (1987; Zbl 0616.10003) Full Text: DOI
Szegedy, M. The solution of Graham’s greatest common divisor problem. (English) Zbl 0593.10002 Combinatorica 6, 67-71 (1986). MSC: 11A05 11A41 PDFBibTeX XMLCite \textit{M. Szegedy}, Combinatorica 6, 67--71 (1986; Zbl 0593.10002) Full Text: DOI
Burosch, Gustav; Gorlow, Waleri Wassiljewitsch; Labahn, Roger; Szegedy, Mario [Gorlov, V. V.] The telephone problem for connnected graphs. (English) Zbl 0569.90023 Elektron. Inform.-verarb. Kybernetik 20, 557-573 (1984). MSC: 90B10 90C35 05C35 PDFBibTeX XMLCite \textit{G. Burosch} et al., Elektron. Informationsverarbeitung Kybernetik 20, 557--573 (1984; Zbl 0569.90023)
Szegedy, M. On the subdivision of the unit square into rectangles with equal area. (English) Zbl 0569.05013 Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. II, Colloq. Math. Soc. János Bolyai 37, 899-902 (1984). MSC: 05B30 PDFBibTeX XML
Szegedy, Márió Une généralisation commune de théorèmes de Fabry et de Paley- Zygmund. (A common generalization of theorems of Fabry and Paley- Zygmund). (French) Zbl 0567.30003 C. R. Acad. Sci., Paris, Sér. I 299, 749-751 (1984). MSC: 30B20 PDFBibTeX XMLCite \textit{M. Szegedy}, C. R. Acad. Sci., Paris, Sér. I 299, 749--751 (1984; Zbl 0567.30003)