Digital Symposium Collection 2000  

 
 
 
 
 
 

 














Noga Alon

Tracking Join and Self-Join Sizes in Limited Storage

Publications

Note: Links lead to the DBLP on the Web.

Noga Alon

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

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

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

77 Noga Alon, Benny Sudakov : On Two Segmentation Problems. J. Algorithms 33 (1): 173-184 (1999)

76 Noga Alon, Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos : Linear Hash Functions. JACM 46 (5): 667-683 (1999)

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

74 Noga Alon: Spectral Techniques in Graph Algorithms. LATIN 1998 : 206-215

73 Noga Alon, Michael Krivelevich , Benny Sudakov : Finding a Large Hidden Clique in a Random Graph. SODA 1998 : 594-598

72 Noga Alon, Yossi Azar , János Csirik , Leah Epstein , Sergey V. Sevastianov , Arjen P. A. Vestjens , Gerhard J. Woeginger : On-Line and Off-Line Approximation Algorithms for Vector Covering Problems. Algorithmica 21 (1): 104-118 (1998)

71 Noga Alon, Yossi Azar , Gerhard J. Woeginger , Tal Yadid : Approximation Schemes for Scheduling. SODA 1997 : 493-500

70 Noga Alon, Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos : Is Linear Hashing Good? STOC 1997 : 465-474

69 Noga Alon, Raphy Yuster , Uri Zwick : Finding and Counting Given Length Cycles. Algorithmica 17 (3): 209-223 (1997)

68 Noga Alon, Aravind Srinivasan : Improved Parallel Approximation of a Class of Integer Programming Problems. Algorithmica 17 (4): 449-462 (1997)

67 Noga Alon, Dmitry N. Kozlov : Coins with Arbitrary Weights. J. Algorithms 25 (1): 162-176 (1997)

66 Noga Alon, Shai Ben-David , Nicolò Cesa-Bianchi , David Haussler : Scale-Sensitive Dimensions, Uniform Convergence, and Learnability. JACM 44 (4): 616-631 (1997)

65 Noga Alon, Zvi Galil , Oded Margalit : On the Exponent of the All Pairs Shortest Path Problem. JCSS 54 (2): 255-262 (1997)

64 Noga Alon, Nabil Kahale : A Spectral Technique for Coloring Random 3-Colorable Graphs. SIAM J. Comput. 26 (6): 1733-1748 (1997)

63 Noga Alon, János Csirik , Sergey V. Sevastianov , Arjen P. A. Vestjens , Gerhard J. Woeginger : On-line and Off-line Approximation Algorithms for Vector Covering Problems. ESA 1996 : 406-418

62 Noga Alon, Dmitry N. Kozlov , Van H. Vu : The Geometry of Coin-Weighing Problems. FOCS 1996 : 524-532

61 Noga Alon, Aravind Srinivasan : Improved Parallel Approximation of a Class of Integer Programming Programming Problems. ICALP 1996 : 562-573

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

59 Noga Alon: Derandomization Via Small Sample Spaces (Abstract). SWAT 1996 : 1-3

58 Noga Alon, Moni Naor : Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Algorithmica 16 (4/5): 434-449 (1996)

57 Noga Alon, Phillip G. Bradford , Rudolf Fleischer : Matching Nuts and Bolts Faster. IPL 59 (3): 123-127 (1996)

56 Noga Alon, Zvi Galil , Moti Yung : Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary. ESA 1995 : 523-537

55 Noga Alon, Jeff Edmonds , Michael Luby : Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). FOCS 1995 : 512-519

54 Noga Alon, Uriel Feige , Avi Wigderson , David Zuckerman : Derandomized Graph Products. Computational Complexity 5 (1): 60-75 (1995)

53 Noga Alon, Sridhar Rajagopalan , Subhash Suri : Long Non-Crossing Configurations in the Plane. Fundamenta Informaticae 22 (4): 385-394 (1995)

52 Noga Alon, Yishay Mansour : varepsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials. IPL 54 (6): 337-342 (1995)

51 Noga Alon, Raphy Yuster , Uri Zwick : Color-Coding. JACM 42 (4): 844-856 (1995)

50 Noga Alon, Richard M. Karp , David Peleg , Douglas West : A Graph-Theoretic Game and Its Application to the k-Server Problem. SIAM J. Comput. 24 (1): 78-100 (1995)

49 Noga Alon, Raphy Yuster , Uri Zwick : Finding and Counting Given Length Cycles (Extended Abstract). ESA 1994 : 354-364

48 Noga Alon, Alan M. Frieze , Dominic Welsh : Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs. FOCS 1994 : 24-35

47 Noga Alon, Manuel Blum , Amos Fiat , Sampath Kannan , Moni Naor , Rafail Ostrovsky : Matching Nuts and Bolts. SODA 1994 : 690-696

46 Noga Alon, Raphy Yuster , Uri Zwick : Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (Extended Abstract). STOC 1994 : 326-335

45 Noga Alon, Nabil Kahale : A spectral technique for coloring random 3-colorable graphs (Preliminary Version). STOC 1994 : 346-355

44 Noga Alon, Alan M. Frieze , Dominic Welsh : Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case. Electronic Colloquium on Computational Complexity (ECCC) 1 (005): (1994)

43 Noga Alon, Raphy Yuster , Uri Zwick : Color-Coding. Electronic Colloquium on Computational Complexity (ECCC) 1 (009): (1994)

42 Noga Alon, Richard A. Duke , Hanno Lefmann , Vojtech Rödl , Raphy Yuster : The Algorithmic Aspects of the Regularity Lemma. J. Algorithms 16 (1): 80-109 (1994)

41 Noga Alon, Nimrod Megiddo : Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. JACM 41 (2): 422-434 (1994)

40 Noga Alon, Pavel Pudlák : Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). JCSS 48 (1): 194-202 (1994)

39 Noga Alon, Gil Kalai , Moty Ricklin , Larry J. Stockmeyer : Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling. TCS 130 (1): 175-201 (1994)

38 Noga Alon, Shai Ben-David , Nicolò Cesa-Bianchi , David Haussler : Scale-sensitive Dimensions, Uniform Convergence, and Learnability. FOCS 1993 : 292-301

37 Noga Alon, Fan R. K. Chung , R. L. Graham : Routing Permutations on Graphs via Matchings (Extended Abstract). STOC 1993 : 583-591

36 Noga Alon, Sridhar Rajagopalan , Subhash Suri : Long Non-Crossing Configurations in the Plane. Symposium on Computational Geometry 1993 : 257-263

35 Pankaj K. Agarwal , Noga Alon, Boris Aronov , Subhash Suri : Can Visibility Graphs be Represented Compactly? Symposium on Computational Geometry 1993 : 338-347

34 Noga Alon, Moni Naor : Coin-Flipping Games Immune Against Linear-Sized Coalitions. SIAM J. Comput. 22 (2): 403-417 (1993)

33 Noga Alon, Gil Kalai , Moty Ricklin , Larry J. Stockmeyer : Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract). FOCS 1992 : 334-343

32 Noga Alon, Zvi Galil , Oded Margalit , Moni Naor : Witnesses for Boolean Matrix Multiplication and for Shortest Paths. FOCS 1992 : 417-426

31 Noga Alon, Richard A. Duke , Hanno Lefmann , Vojtech Rödl , Raphy Yuster : The Algorithmic Aspects of the Regularity Lemma (Extended Abstract). FOCS 1992 : 473-481

30 Miklós Ajtai , Noga Alon, Jehoshua Bruck , Robert Cypher , Ching-Tien Ho , Moni Naor , Endre Szemerédi : Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths. FOCS 1992 : 693-702

29 Noga Alon, Yossi Azar : Comparison-Sorting and Selecting in Totally Monotone Matrices. SODA 1992 : 403-408

28 Noga Alon, Daniel J. Kleitman : Piercing Convex Sets. Symposium on Computational Geometry 1992 : 157-160

27 Noga Alon, Yossi Azar : On-Line Steiner Trees in the Euclidean Plane. Symposium on Computational Geometry 1992 : 337-343

26 Noga Alon, Amotz Bar-Noy , Nathan Linial , David Peleg : Single Round Simulation on Radio Networks. J. Algorithms 13 (2): 188-210 (1992)

25 Noga Alon, Zvi Galil , Oded Margalit : On the Exponent of the All Pairs Shortest Path Problem. FOCS 1991 : 569-575

24 Noga Alon: A parallel algorithmic version of the Local Lemma. FOCS 1991 : 586-593

23 Noga Alon, A. K. Dewdney , Teunis J. Ott : Efficient Simulation of Finite Automata by Neural Nets. JACM 38 (2): 495-514 (1991)

22 Noga Alon, Amotz Bar-Noy , Nathan Linial , David Peleg : A Lower Bound for Radio Broadcast. JCSS 43 (2): 290-298 (1991)

21 Noga Alon, Moni Naor : Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract). FOCS 1990 : 46-54

20 Noga Alon, Oded Goldreich , Johan Håstad , René Peralta : Simple Constructions of Almost k-Wise Independent Random Variables. FOCS 1990 : 544-553

19 Noga Alon, Nimrod Megiddo : Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. FOCS 1990 : 574-582

18 Noga Alon, Paul Seymour , Robin Thomas : A Separator Theorem for Graphs with an Excluded Minor and its Applications. STOC 1990 : 293-299

17 Noga Alon: Generating Pseudo-Random Permutations and Maximum Flow Algorithms. IPL 35 (4): 201-204 (1990)

16 Noga Alon, Mauricio Karchmer , Avi Wigderson : Linear Circuits over GF(2). SIAM J. Comput. 19 (6): 1064-1067 (1990)

15 Noga Alon, Amotz Bar-Noy , Nathan Linial , David Peleg : On the Complexity of Radio Communication (Extended Abstract). STOC 1989 : 274-285

14 Noga Alon, Yossi Azar : Finding an Approximate Maximum. SIAM J. Comput. 18 (2): 258-267 (1989)

13 Noga Alon, Uri Zwick : On Neciporuk's Theorem for Branching Programs. TCS 64 (3): 331-342 (1989)

12 Noga Alon, Yossi Azar : Parallel Comparison Algorithms for Approximation Problems. FOCS 1988 : 194-203

11 Noga Alon, Wolfgang Maass : Meanders and Their Applications in Lower Bounds Arguments. JCSS 37 (2): 118-129 (1988)

10 Noga Alon, Yossi Azar : The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms. SIAM J. Comput. 17 (6): 1178-1192 (1988)

9 Noga Alon, Yossi Azar : The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms. FOCS 1987 : 489-498

8 Noga Alon, David Haussler , Emo Welzl : Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension. Symposium on Computational Geometry 1987 : 331-340

7 Noga Alon, Zvi Galil , V. D. Milman : Better Expanders and Superconcentrators. J. Algorithms 8 (3): 337-347 (1987)

6 Noga Alon, Wolfgang Maass : Meanders, Ramsey Theory and Lower Bounds for Branching Programs. FOCS 1986 : 410-417

5 Noga Alon, Yossi Azar , Uzi Vishkin : Tight Complexity Bounds for Parallel Comparison Sorting. FOCS 1986 : 502-510

4 Noga Alon, László Babai , Alon Itai : A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms 7 (4): 567-583 (1986)

3 Noga Alon, P. Frankl , Vojtech Rödl : Geometrical Realization of Set Systems and Probabilistic Communication Complexity. FOCS 1985 : 277-280

2 Noga Alon: Expanders, Sorting in Rounds and Superconcentrators of Limited Depth. STOC 1985 : 98-102

1 Noga Alon, V. D. Milman : Eigenvalues, Expanders and Superconcentrators (Extended Abstract). FOCS 1984 : 320-322



























Copyright(C) 2000 ACM