Vita and On-line Papers
Publications available on-line:
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
-
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
Combinatorics and Combinatorial Number Theory