Digital Symposium Collection 2000  

 
 
 
 
 
 

 














Mario Szegedy

Tracking Join and Self-Join Sizes in Limited Storage

Publications

Note: Links lead to the DBLP on the Web.

Mario Szegedy

39 Noga Alon , Michael Krivelevich , Ilan Newman , Mario Szegedy: Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999 : 645-655

38 Noga Alon , Eldar Fischer , Michael Krivelevich , Mario Szegedy: Efficient Testing of Large Graphs. FOCS 1999 : 656-666

37 Mario Szegedy: Many-Valued Logics and Holographic Proofs. ICALP 1999 : 676-686

36 Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy: Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999 : 10-20

35 Haim Kaplan , Mario Szegedy: On-line Complexity of Monotone Set Systems. SODA 1999 : 507-516

34 David S. Johnson , Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999 : 927-928

33 Haim Kaplan , Martin Strauss , Mario Szegedy: Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA 1999 : 935-936

32 Mario Szegedy: A Slique Size Bounding Technique with Application to Non-Linear Codes. SODA 1999 : 971-972

31 Mario Szegedy: In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? STACS 1999 : 341-346

30 Noga Alon , Yossi Matias , Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. JCSS 58 (1): 137-147 (1999)

29 Mario Szegedy: Algorithms to Tile the Infinite Grid with Finite Clusters. FOCS 1998 : 137-147

28 Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy: Proof verification and the hardness of approximation problems. Electronic Colloquium on Computational Complexity (ECCC) 5 (008): (1998)

27 Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy: Proof Verification and the Hardness of Approximation Problems. JACM 45 (3): 501-555 (1998)

26 Noga Alon , Yossi Matias , Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. STOC 1996 : 20-29

25 Ilan Newman , Mario Szegedy: Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996 : 561-570

24 János Pach , Farhad Shahrokhi , Mario Szegedy: Applications of the Crossing Number. Algorithmica 16 (1): 111-117 (1996)

23 Uriel Feige , Shafi Goldwasser , László Lovász , Shmuel Safra , Mario Szegedy: Interactive Proofs and the Hardness of Approximating Cliques. JACM 43 (2): 268-292 (1996)

22 Anna Gál , Mario Szegedy: Fault Tolerant Circuits and Probabilistically Checkable Proofs. Structure in Complexity Theory Conference 1995 : 65-73

21 László Lovász , János Pach , Mario Szegedy: On Conway's Thrackle Conjecture. Symposium on Computational Geometry 1995 : 147-151

20 Mario Szegedy: A note on the Theta number of Lovász and the generalized Delsarte bound. FOCS 1994 : 36-39

19 János Pach , Farhad Shahrokhi , Mario Szegedy: Applications of the Crossing Number. Symposium on Computational Geometry 1994 : 198-202

18 Noam Nisan , Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4 : 301-313 (1994)

17 Magnús M. Halldórsson , Mario Szegedy: Lower Bounds for On-Line Graph Coloring. TCS 130 (1): 163-174 (1994)

16 Mario Szegedy, Sundar Vishwanathan : Locality Based Graph Coloring. STOC 1993 : 201-207

15 András Hajnal , Wolfgang Maass , Pavel Pudlák , Mario Szegedy, György Turán : Threshold Circuits of Bounded Depth. JCSS 46 (2): 129-154 (1993)

14 Mario Szegedy: Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. JCSS 47 (3): 405-423 (1993)

13 Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy: Proof Verification and Hardness of Approximation Problems. FOCS 1992 : 14-23

12 Magnús M. Halldórsson , Mario Szegedy: Lower Bounds for On-Line Graph Coloring. SODA 1992 : 211-216

11 Noam Nisan , Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. STOC 1992 : 462-467

10 Janos Simon , Mario Szegedy: On the Complexity of RAM with Various Operation Sets. STOC 1992 : 624-631

9 Lance Fortnow , Mario Szegedy: On the Power of Two-Local Random Reductions. IPL 44 (6): 303-306 (1992)

8 László Babai , Noam Nisan , Mario Szegedy: Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. JCSS 45 (2): 204-232 (1992)

7 Lance Fortnow , Mario Szegedy: On the Power of Two-Local Random Reductions. ASIACRYPT 1991 : 346-351

6 Uriel Feige , Shafi Goldwasser , László Lovász , Shmuel Safra , Mario Szegedy: Approximating Clique is Almost NP-Complete (Preliminary Version). FOCS 1991 : 2-12

5 László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy: Checking Computations in Polylogarithmic Time. STOC 1991 : 21-31

4 Mario Szegedy: Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates. STOC 1990 : 278-286

3 László Babai , Noam Nisan , Mario Szegedy: Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract). STOC 1989 : 1-11

2 David Rubinstein , Jeffrey Shallit , Mario Szegedy: A Subset Coloring Algorithm and Its Applications to Computer Graphics. CACM 31 (10): 1228-1232 (1988)

1 András Hajnal , Wolfgang Maass , Pavel Pudlák , Mario Szegedy, György Turán : Threshold circuits of bounded depth. FOCS 1987 : 99-110



























Copyright(C) 2000 ACM