No photo of Mario Szegedy

View Scopus Profile

Mario Szegedy

Calculated based on number of publications stored in Pure and citations from Scopus
1986 …2024

Research activity per year

Filter
Conference contribution

Search results

  • 2022

    Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning

    Guo, T., Feng, S. W., Szegedy, M. & Yu, J., 2022, 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022. Institute of Electrical and Electronics Engineers Inc., (2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 2017

    The moser-tardos resample algorithm: Where is the limit? (an experimental inquiry)

    Catarata, J. D., Corbett, S., Stern, H., Szegedy, M., Vyskocil, T. & Zhang, Z., 2017, 19th Workshop on Algorithm Engineering and Experiments 2017, ALENEX 2017. Fekete, S. & Ramachandran, V. (eds.). Society for Industrial and Applied Mathematics Publications, p. 159-171 13 p. (Proceedings of the Workshop on Algorithm Engineering and Experiments; vol. 0).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    7 Scopus citations
  • 2014

    Local tests of global entanglement and a counterexample to the generalized area law

    Aharonov, D., Harrow, A. W., Landau, Z., Nagaj, D., Szegedy, M. & Vazirani, U., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 246-255 10 p. 6979009. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    21 Scopus citations

  • The garden hose complexity for the equality function

    Chiu, W. Y., Szegedy, M., Wang, C. & Xu, Y., 2014, Algorithmic Aspects in Information and Management - 10th International Conference, AAIM 2014, Proceedings. Springer Verlag, p. 112-123 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8546 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    4 Scopus citations
  • 2013

    Digital signatures with minimal overhead from indifferentiable random invertible functions

    Kiltz, E., Pietrzak, K. & Szegedy, M., 2013, Advances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings. PART 1 ed. p. 571-588 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8042 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    13 Scopus citations

  • The lovász local lemma-A survey

    Szegedy, M., 2013, Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013. Springer Verlag, p. 1-11 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7913 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    20 Scopus citations
  • 2012

    A sharper local lemma with improved applications

    Kolipaka, K., Szegedy, M. & Xu, Y., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 603-614 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    19 Scopus citations

  • Mechanism design: From partial to probabilistic verification

    Caragiannis, I., Elkind, E., Szegedy, M. & Yu, L., 2012, EC '12 - Proceedings of the 13th ACM Conference on Electronic Commerce. p. 266-283 18 p. (Proceedings of the ACM Conference on Electronic Commerce).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    28 Scopus citations

  • Streaming and communication complexity of clique approximation

    Halldórsson, M. M., Sun, X., Szegedy, M. & Wang, C., 2012, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. p. 449-460 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7391 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    18 Scopus citations
  • 2011

    Moser and Tardos meet Lovász

    Kolipaka, K. B. R. & Szegedy, M., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 235-243 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    70 Scopus citations

  • Quantum query complexity of state conversion

    Lee, T., Mittal, R., Reichardt, B. W., Špalek, R. & Szegedy, M., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 344-353 10 p. 6108195. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    102 Scopus citations
  • 2010

    Streaming algorithms for independent sets

    Halldórsson, B. V., Halldórsson, M. M., Losievskaja, E. & Szegedy, M., 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 641-652 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    17 Scopus citations
  • 2009

    Amortized communication complexity of distributions

    Roland, J. & Szegedy, M., 2009, Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. p. 738-749 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5555 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations

  • A new line of attack on the dichotomy conjecture

    Kun, G. & Szegedy, M., 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 725-734 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    20 Scopus citations
  • 2008

    Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

    Chen, X., Pach, J., Szegedy, M. & Tardos, G., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 94-101 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    8 Scopus citations

  • Parallel repetition of the odd cycle game

    Azimian, K. & Szegedy, M., 2008, LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. p. 676-686 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4957 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Scopus citations
  • 2007

    Languages with bounded multiparty communication complexity

    Chattopadhyay, A., Krebs, A., Koucký, M., Szegedy, M., Tesson, P. & Thérien, D., 2007, STACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, p. 500-511 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4393 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    8 Scopus citations

  • Product rules in semidefinite programming

    Mittal, R. & Szegedy, M., 2007, Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings. Springer Verlag, p. 435-445 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4639 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    13 Scopus citations
  • 2006

    A dichotomy theorem for typed constraint satisfaction problems

    Chen, S., Imielinski, T., Johnsgard, K., Smith, D. & Szegedy, M., 2006, Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings. Springer Verlag, p. 226-239 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4121 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations

  • The DLT priority sampling is essentially optimal

    Szegedy, M., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 150-158 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    35 Scopus citations
  • 2002

    Computing Boolean functions from multiple faulty copies of input bits

    Szegedy, M. & Chen, X., 2002, LATIN 2002: Theoretical Informatics - 5th Latin American Symposium, Proceedings. Rajsbaum, S. (ed.). Springer Verlag, p. 539-553 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2286).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    6 Scopus citations
  • 1999

    In how many steps the k peg version of the towers of hanoi game can be solved

    Szegedy, M., 1999, STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Meinel, C. & Tison, S. (eds.). Springer Verlag, p. 356-361 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1563).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    30 Scopus citations

  • Many-valued logics and holographic proofs

    Szegedy, M., 1999, Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings. Springer Verlag, p. 676-686 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1644 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    20 Scopus citations
  • 1996

    Public vs. private coin flips in one round communication games

    Newman, I. & Szegedy, M., Jul 1 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 561-570 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    78 Scopus citations

  • The space complexity of approximating the frequency moments

    Alon, N., Matias, Y. & Szegedy, M., Jul 1 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 20-29 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    606 Scopus citations
  • 1995

    On conway's thrackle conjecture

    Lovász, L., Pach, J. & Szegedy, M., Sep 1 1995, Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995. Association for Computing Machinery, p. 147-151 5 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. Part F129372).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Scopus citations
  • 1994

    Applications of the crossing number

    Pach, J., Shahrokhi, F. & Szegedy, M., 1994, Proceedings of the Annual Symposium on Computational Geometry. Publ by ACM, p. 198-202 5 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    24 Scopus citations
  • 1993

    Locality based graph coloring

    Szegecly, M. & Visbwanathan, S., Jun 1 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 201-207 7 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    67 Scopus citations

  • On the power of two-local random reductions

    Fortnow, L. & Szegedy, M., 1993, Advances in Cryptology ─ ASIACRYPT 1991 - International Conference on the Theory and Application of Cryptology, Proceedings. Imai, H., Matsumoto, T. & Rivest, R. L. (eds.). Springer Verlag, p. 346-351 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 739 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations
  • 1992

    Lower bounds for on-line graph coloring

    Halldórsson, M. M. & Szegedy, M., Sep 1 1992, Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992. Association for Computing Machinery, p. 211-216 6 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129721).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    26 Scopus citations

  • On the complexity of RAM with various operation sets

    Simon, J. & Szegedy, M., Jul 1 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 624-631 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    5 Scopus citations

  • On the degree of boolean functions as real polynomials

    Nisan, N. & Szegedy, M., Jul 1 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 462-467 6 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    52 Scopus citations

  • Proof verification and hardness of approximation problems

    Arora, S., Lund, C., Motwani, R., Sudan, M. & Szegedy, M., 1992, Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992. IEEE Computer Society, p. 14-23 10 p. 267823. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 1992-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    456 Scopus citations
  • 1991

    Approximating clique is almost NP-complete

    Feige, U., Goldwasser, S., Lovasz, L., Safra, S. & Szegedy, M., Dec 1991, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 2-12 11 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    214 Scopus citations

  • Checking computations in polylogarithmic time

    Babai, L., Fortnow, L., Levin, L. A. & Szegedy, M., Jan 3 1991, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991. Association for Computing Machinery, p. 21-42 22 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F130073).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    419 Scopus citations
  • 1990

    Functions with bounded symmetric communication complexity and circuits with MOD m gates

    Szegedy, M., 1990, Proc 22nd Annu ACM Symp Theory Comput. Publ by ACM, p. 278-286 9 p. (Proc 22nd Annu ACM Symp Theory Comput).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    5 Scopus citations
  • 1989

    Multiparty protocols and Logspace-hard pseudorandom sequences

    Babai, L., Nisan, N. & Szegedy, M., 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 1-11 11 p. (Proc Twenty First Annu ACM Symp Theory Comput).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    60 Scopus citations
  • 1987

    THRESHOLD CIRCUITS OF BOUNDED DEPTH.

    Hajnal, A., Maass, W., Pudlak, P., Szegedy, M. & Turan, G., 1987, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 99-110 12 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    103 Scopus citations