The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Mario Szegedy: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Noga Alon, Yossi Matias, Mario Szegedy
    The Space Complexity of Approximating the Frequency Moments. [Citation Graph (4, 0)][DBLP]
    STOC, 1996, pp:20-29 [Conf]
  2. Lance Fortnow, Mario Szegedy
    On the Power of Two-Local Random Reductions. [Citation Graph (0, 0)][DBLP]
    ASIACRYPT, 1991, pp:346-351 [Conf]
  3. Howard Barnum, Michael E. Saks, Mario Szegedy
    Quantum query complexity and semi-definite programming. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2003, pp:179-193 [Conf]
  4. Anna Gál, Mario Szegedy
    Fault Tolerant Circuits and Probabilistically Checkable Proofs. [Citation Graph (0, 0)][DBLP]
    Structure in Complexity Theory Conference, 1995, pp:65-73 [Conf]
  5. Sophie Laplante, Troy Lee, Mario Szegedy
    The Quantum Adversary Method and Classical Formula Size Lower Bounds. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2005, pp:76-90 [Conf]
  6. Xiaomin Chen, Mario Szegedy, Lei Wang
    Optimally Balanced Forward Degree Sequence. [Citation Graph (0, 0)][DBLP]
    COCOON, 2005, pp:680-689 [Conf]
  7. József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
    Long monotone paths in line arrangements. [Citation Graph (0, 0)][DBLP]
    Symposium on Computational Geometry, 2003, pp:124-128 [Conf]
  8. László Lovász, János Pach, Mario Szegedy
    On Conway's Thrackle Conjecture. [Citation Graph (0, 0)][DBLP]
    Symposium on Computational Geometry, 1995, pp:147-151 [Conf]
  9. János Pach, Farhad Shahrokhi, Mario Szegedy
    Applications of the Crossing Number. [Citation Graph (0, 0)][DBLP]
    Symposium on Computational Geometry, 1994, pp:198-202 [Conf]
  10. Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
    Efficient Testing of Large Graphs. [Citation Graph (0, 0)][DBLP]
    FOCS, 1999, pp:656-666 [Conf]
  11. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
    Regular Languages Are Testable with a Constant Number of Queries. [Citation Graph (0, 0)][DBLP]
    FOCS, 1999, pp:645-655 [Conf]
  12. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
    Proof Verification and Hardness of Approximation Problems [Citation Graph (0, 0)][DBLP]
    FOCS, 1992, pp:14-23 [Conf]
  13. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
    Approximating Clique is Almost NP-Complete (Preliminary Version) [Citation Graph (0, 0)][DBLP]
    FOCS, 1991, pp:2-12 [Conf]
  14. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán
    Threshold circuits of bounded depth [Citation Graph (0, 0)][DBLP]
    FOCS, 1987, pp:99-110 [Conf]
  15. Mario Szegedy
    Quantum Speed-Up of Markov Chain Based Algorithms. [Citation Graph (0, 0)][DBLP]
    FOCS, 2004, pp:32-41 [Conf]
  16. Mario Szegedy
    A note on the Theta number of Lovász and the generalized Delsarte bound [Citation Graph (0, 0)][DBLP]
    FOCS, 1994, pp:36-39 [Conf]
  17. Mario Szegedy
    Algorithms to Tile the Infinite Grid with Finite Clusters. [Citation Graph (0, 0)][DBLP]
    FOCS, 1998, pp:137-147 [Conf]
  18. Robert Spalek, Mario Szegedy
    All Quantum Adversary Methods Are Equivalent. [Citation Graph (0, 0)][DBLP]
    ICALP, 2005, pp:1299-1311 [Conf]
  19. Mario Szegedy
    Many-Valued Logics and Holographic Proofs. [Citation Graph (0, 0)][DBLP]
    ICALP, 1999, pp:676-686 [Conf]
  20. Mario Szegedy, Xiaomin Chen
    Computing Boolean Functions from Multiple Faulty Copies of Input Bits. [Citation Graph (0, 0)][DBLP]
    LATIN, 2002, pp:539-553 [Conf]
  21. Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
    Tracking Join and Self-Join Sizes in Limited Storage. [Citation Graph (0, 17)][DBLP]
    PODS, 1999, pp:10-20 [Conf]
  22. Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy
    A Dichotomy Theorem for Typed Constraint Satisfaction Problems. [Citation Graph (0, 0)][DBLP]
    SAT, 2006, pp:226-239 [Conf]
  23. Magnús M. Halldórsson, Mario Szegedy
    Lower Bounds for On-Line Graph Coloring. [Citation Graph (0, 0)][DBLP]
    SODA, 1992, pp:211-216 [Conf]
  24. David S. Johnson, Mario Szegedy
    What are the Least Tractable Instances of max Tndependent Set? [Citation Graph (0, 0)][DBLP]
    SODA, 1999, pp:927-928 [Conf]
  25. Haim Kaplan, Mario Szegedy
    On-line Complexity of Monotone Set Systems. [Citation Graph (0, 0)][DBLP]
    SODA, 1999, pp:507-516 [Conf]
  26. Haim Kaplan, Martin Strauss, Mario Szegedy
    Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. [Citation Graph (0, 0)][DBLP]
    SODA, 1999, pp:935-936 [Conf]
  27. Frédéric Magniez, Miklos Santha, Mario Szegedy
    Quantum algorithms for the triangle problem. [Citation Graph (0, 0)][DBLP]
    SODA, 2005, pp:1109-1117 [Conf]
  28. Mario Szegedy
    A Slique Size Bounding Technique with Application to Non-Linear Codes. [Citation Graph (0, 0)][DBLP]
    SODA, 1999, pp:971-972 [Conf]
  29. Mario Szegedy
    In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? [Citation Graph (0, 0)][DBLP]
    STACS, 1999, pp:356-361 [Conf]
  30. Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
    Languages with Bounded Multiparty Communication Complexity. [Citation Graph (0, 0)][DBLP]
    STACS, 2007, pp:500-511 [Conf]
  31. László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
    Checking Computations in Polylogarithmic Time [Citation Graph (0, 0)][DBLP]
    STOC, 1991, pp:21-31 [Conf]
  32. László Babai, Noam Nisan, Mario Szegedy
    Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) [Citation Graph (0, 0)][DBLP]
    STOC, 1989, pp:1-11 [Conf]
  33. Ilan Newman, Mario Szegedy
    Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1996, pp:561-570 [Conf]
  34. Noam Nisan, Mario Szegedy
    On the Degree of Boolean Functions as Real Polynomials [Citation Graph (0, 0)][DBLP]
    STOC, 1992, pp:462-467 [Conf]
  35. Miklos Santha, Mario Szegedy
    Quantum and classical query complexities of local search are polynomially related. [Citation Graph (0, 0)][DBLP]
    STOC, 2004, pp:494-501 [Conf]
  36. Mario Szegedy
    The DLT priority sampling is essentially optimal. [Citation Graph (0, 0)][DBLP]
    STOC, 2006, pp:150-158 [Conf]
  37. Mario Szegedy
    Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates [Citation Graph (0, 0)][DBLP]
    STOC, 1990, pp:278-286 [Conf]
  38. Mario Szegedy, Sundar Vishwanathan
    Locality based graph coloring. [Citation Graph (0, 0)][DBLP]
    STOC, 1993, pp:201-207 [Conf]
  39. Janos Simon, Mario Szegedy
    On the Complexity of RAM with Various Operation Sets [Citation Graph (0, 0)][DBLP]
    STOC, 1992, pp:624-631 [Conf]
  40. János Pach, Farhad Shahrokhi, Mario Szegedy
    Applications of the Crossing Number. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 1996, v:16, n:1, pp:111-117 [Journal]
  41. David Rubinstein, Jeffrey Shallit, Mario Szegedy
    A Subset Coloring Algorithm and Its Applications to Computer Graphics. [Citation Graph (0, 0)][DBLP]
    Commun. ACM, 1988, v:31, n:10, pp:1228-1232 [Journal]
  42. Sophie Laplante, Troy Lee, Mario Szegedy
    The Quantum Adversary Method and Classical Formula Size Lower Bounds. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2006, v:15, n:2, pp:163-196 [Journal]
  43. Noam Nisan, Mario Szegedy
    On the Degree of Boolean Functions as Real Polynomials. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1994, v:4, n:, pp:301-313 [Journal]
  44. Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
    Efficient Testing of Large Graphs. [Citation Graph (0, 0)][DBLP]
    Combinatorica, 2000, v:20, n:4, pp:451-476 [Journal]
  45. Péter Hajnal, Mario Szegedy
    On packing bipartite graphs. [Citation Graph (0, 0)][DBLP]
    Combinatorica, 1992, v:12, n:3, pp:295-301 [Journal]
  46. Mario Szegedy
    The solution of Graham's greatest common divisor problem. [Citation Graph (0, 0)][DBLP]
    Combinatorica, 1986, v:6, n:1, pp:67-71 [Journal]
  47. László Babai, Mario Szegedy
    Local Expansion of Ssymmetrical Graphs. [Citation Graph (0, 0)][DBLP]
    Combinatorics, Probability & Computing, 1992, v:1, n:, pp:1-11 [Journal]
  48. József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
    Long Monotone Paths in Line Arrangements. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 2004, v:32, n:2, pp:167-176 [Journal]
  49. László Lovász, János Pach, Mario Szegedy
    On Conway's Thrackle Conjecture. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 1997, v:18, n:4, pp:369-376 [Journal]
  50. Mario Szegedy
    Near optimality of the priority sampling procedure [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:001, pp:- [Journal]
  51. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
    Proof verification and the hardness of approximation problems. [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:8, pp:- [Journal]
  52. Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy
    The Telephone Problem for Connected Graphs. [Citation Graph (0, 0)][DBLP]
    Elektronische Informationsverarbeitung und Kybernetik, 1984, v:20, n:10/11, pp:557-573 [Journal]
  53. Lance Fortnow, Mario Szegedy
    On the Power of Two-Local Random Reductions. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1992, v:44, n:6, pp:303-306 [Journal]
  54. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
    Proof Verification and the Hardness of Approximation Problems. [Citation Graph (0, 0)][DBLP]
    J. ACM, 1998, v:45, n:3, pp:501-555 [Journal]
  55. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
    Interactive Proofs and the Hardness of Approximating Cliques. [Citation Graph (0, 0)][DBLP]
    J. ACM, 1996, v:43, n:2, pp:268-292 [Journal]
  56. Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
    Tracking Join and Self-Join Sizes in Limited Storage. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2002, v:64, n:3, pp:719-747 [Journal]
  57. Noga Alon, Yossi Matias, Mario Szegedy
    The Space Complexity of Approximating the Frequency Moments. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1999, v:58, n:1, pp:137-147 [Journal]
  58. László Babai, Noam Nisan, Mario Szegedy
    Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1992, v:45, n:2, pp:204-232 [Journal]
  59. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán
    Threshold Circuits of Bounded Depth. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1993, v:46, n:2, pp:129-154 [Journal]
  60. Mario Szegedy
    Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1993, v:47, n:3, pp:405-423 [Journal]
  61. Noga Alon, Eldar Fischer, Mario Szegedy
    Parent-Identifying Codes. [Citation Graph (0, 0)][DBLP]
    J. Comb. Theory, Ser. A, 2001, v:95, n:2, pp:349-359 [Journal]
  62. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
    Regular Languages are Testable with a Constant Number of Queries. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:30, n:6, pp:1842-1862 [Journal]
  63. Frédéric Magniez, Miklos Santha, Mario Szegedy
    Quantum Algorithms for the Triangle Problem. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2007, v:37, n:2, pp:413-424 [Journal]
  64. Magnús M. Halldórsson, Mario Szegedy
    Lower Bounds for On-Line Graph Coloring. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1994, v:130, n:1, pp:163-174 [Journal]
  65. Mario Szegedy, Xiaomin Chen
    Computing Boolean functions from multiple faulty copies of input bits. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2004, v:321, n:1, pp:149-170 [Journal]
  66. Mario Szegedy, Mikkel Thorup
    On the Variance of Subset Sum Estimation. [Citation Graph (0, 0)][DBLP]
    ESA, 2007, pp:75-86 [Conf]
  67. Rajat Mittal, Mario Szegedy
    Product Rules in Semidefinite Programming. [Citation Graph (0, 0)][DBLP]
    FCT, 2007, pp:435-445 [Conf]
  68. Mario Szegedy, Mikkel Thorup
    On the variance of subset sum estimation [Citation Graph (0, 0)][DBLP]
    CoRR, 2007, v:0, n:, pp:- [Journal]

  69. Six-way equipartitioning by three lines in the plane. [Citation Graph (, )][DBLP]


  70. Amortized Communication Complexity of Distributions. [Citation Graph (, )][DBLP]


  71. Streaming Algorithms for Independent Sets. [Citation Graph (, )][DBLP]


  72. Parallel Repetition of the Odd Cycle Game. [Citation Graph (, )][DBLP]


  73. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. [Citation Graph (, )][DBLP]


  74. A new line of attack on the dichotomy conjecture. [Citation Graph (, )][DBLP]


  75. Quantum and Classical Query Complexities of Local Search Are Polynomially Related. [Citation Graph (, )][DBLP]


  76. Geometric representation of cubic graphs with four directions. [Citation Graph (, )][DBLP]


  77. Languages with Bounded Multiparty Communication Complexity. [Citation Graph (, )][DBLP]


Search in 0.099secs, Finished in 0.102secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002