Vita and On-line Papers

My vita in postscript (including a list of publications)

Computer Science

• Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy: Regular Languages are Testable with a Constant Number of Queries
• Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy: Efficient Testing of Large Graphs
• Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy: Tracking Join and Self-Join Sizes in Limited Storage
• Haim Kaplan and Mario Szegedy: On-line complexity of monotone set systems
• David S. Johnson and Mario Szegedy: What are the least tractable instances of max independent set?
• Haim Kaplan, Martin Strauss, Mario Szegedy: Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.
• Mario Szegedy: A clique size bounding technique with application to non-linear codes
• Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and the Hardness of Approximation Problems
• Ilan Newman, Mario Szegedy: Public vs. Private Coin Flips in One Round Communication Games
• Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy: Interactive Proofs and the Hardness of Approximating Cliques
• Anna Gál, Mario Szegedy: Fault Tolerant Circuits and Probabilistically Checkable Proofs
• Mario Szegedy: A note on the Theta number of Lovász and the generalized Delsarte bound
• Local copy
• Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials
• Magnús M. Halldórsson, Mario Szegedy: Lower Bounds for On-Line Graph Coloring
• Mario Szegedy, Sundar Vishwanathan: Locality Based Graph Coloring
• András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán: Threshold Circuits of Bounded Depth
• Mario Szegedy: Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC
• Janos Simon, Mario Szegedy: On the Complexity of RAM with Various Operation Sets
• Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions
• László Babai, Noam Nisan, Mario Szegedy: Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Tradeoffs
• László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time

Geometry

• Mario Szegedy: Algorithms to Tile the Infinite Grid with Finite Clusters
• Local copy
• János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number
• László Lovász, János Pach, Mario Szegedy: On Conway's Thrackle Conjecture

Combinatorics and Combinatorial Number Theory

• M. Szegedy, G. Tardos: On the decomposition of infinite series into monotone decreasing parts
• Mario Szegedy: In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?
• Local copy
• L. Babai and M. Szegedy: Local expansion in symmetrical graphs
• Noga Alon, Mario Szegedy: Large Sets of Nearly Orthogonal Vectors
• Local copy