`Travelled to:`

1 × Finland

1 × Germany

1 × Greece

1 × Iceland

1 × Italy

1 × Poland

1 × Switzerland

17 × USA

2 × Canada

`Collaborated with:`

A.Shapira A.Naor B.Sudakov Y.Matias M.Szegedy S.Saurabh R.Hod S.Gutner V.Asodi A.Srinivasan N.Kahale ∅ M.Krivelevich T.Milo F.Neven D.Suciu V.Vianu A.Moitra D.Lokshtanov A.Agarwal M.Charikar R.Yuster U.Zwick F.R.K.Chung R.L.Graham P.D.Seymour R.Thomas T.Lee A.Shraibman S.Vempala E.Fischer I.Newman N.G.Duffield C.Lund M.Thorup K.Makarychev Y.Makarychev W.F.d.l.Vega R.Kannan M.Karpinski P.B.Gibbons A.Bar-Noy N.Linial D.Peleg F.V.Fomin G.Gutin B.Awerbuch Y.Azar N.Buchbinder J.Naor H.Kaplan D.Malkhi J.P.Stern M.Dietzfelbinger P.B.Miltersen E.Petrank G.Tardos A.Coja-Oghlan H.Hàn M.Kang V.Rödl M.Schacht A.Andoni T.Kaufman K.Matulef R.Rubinfeld N.Xie

`Talks about:`

graph (10) approxim (8) problem (6) applic (4) algorithm (3) subgraph (3) random (3) direct (3) color (3) typecheck (2)

## Person: Noga Alon

### DBLP: Alon:Noga

### Contributed to:

### Wrote 32 papers:

- STOC-2013-AlonLSV #algorithm #approximate #matrix #rank
- The approximate rank of a matrix and its algorithmic applications: approximate rank (NA, TL, AS, SV), pp. 675–684.
- STOC-2012-AlonMS #graph #scalability
- Nearly complete graphs decomposable into large induced matchings and their applications (NA, AM, BS), pp. 1079–1090.
- ICALP-v1-2009-AlonLS #performance
- Fast FAST (NA, DL, SS), pp. 49–58.
- ICALP-A-2008-AlonH #encoding
- Optimal Monotone Encodings (NA, RH), pp. 258–270.
- ICALP-2007-AlonCHKRS #algorithm #graph
- Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions (NA, ACO, HH, MK, VR, MS), pp. 789–800.
- ICALP-2007-AlonFGKS #algorithm #problem
- Parameterized Algorithms for Directed Maximum Leaf Problems (NA, FVF, GG, MK, SS), pp. 352–362.
- ICALP-2007-AlonG #product line
- Balanced Families of Perfect Hash Functions and Their Applications (NA, SG), pp. 435–446.
- STOC-2007-AgarwalAC #approximate #problem
- Improved approximation for directed cut problems (AA, NA, MC), pp. 671–680.
- STOC-2007-AlonAKMRX #independence #testing
- Testing k-wise and almost k-wise independence (NA, AA, TK, KM, RR, NX), pp. 496–505.
- ICALP-v1-2006-AlonSS #approximate #problem
- Additive Approximation for Edge-Deletion Problems (NA, AS, BS), pp. 1–2.
- STOC-2006-Shapira #all about #combinator #graph
- A combinatorial characterization of the testable graph properties: it’s all about regularity (NA, EF, IN, AS), pp. 251–260.
- PODS-2005-AlonDLT #set
- Estimating arbitrary subset sums with few probes (NA, NGD, CL, MT), pp. 317–325.
- STOC-2005-AlonMMN #graph #polynomial
- Quadratic forms on graphs (NA, KM, YM, AN), pp. 486–493.
- STOC-2005-AlonS #graph
- Every monotone graph property is testable (NA, AS), pp. 128–137.
- ICALP-2004-AlonA #learning
- Learning a Hidden Subgraph (NA, VA), pp. 110–121.
- STOC-2004-AlonN #approximate #difference
- Approximating the cut-norm via Grothendieck’s inequality (NA, AN), pp. 72–80.
- STOC-2003-AlonAA #online #problem #set
- The online set cover problem (NA, BA, YA, NB, JN), pp. 100–105.
- STOC-2003-AlonS #graph #testing
- Testing subgraphs in directed graphs (NA, AS), pp. 700–709.
- STOC-2002-AlonVKK #approximate #problem #random
- Random sampling and approximation of MAX-CSP problems (NA, WFdlV, RK, MK), pp. 232–239.
- LICS-2001-AlonMNSV #database #relational #xml
- Typechecking XML Views of Relational Databases (NA, TM, FN, DS, VV), pp. 421–430.
- PODS-2001-AlonMNSV #revisited #xml
- XML with Data Values: Typechecking Revisited (NA, TM, FN, DS, VV).
- ICALP-2000-AlonKKMS #scalability
- Scalable Secure Storage when Half the System Is Faulty (NA, HK, MK, DM, JPS), pp. 576–587.
- PODS-1999-AlonGMS #self
- Tracking Join and Self-Join Sizes in Limited Storage (NA, PBG, YM, MS), pp. 10–20.
- STOC-1997-AlonDMPT #linear #question
- Is Linear Hashing Good? (NA, MD, PBM, EP, GT), pp. 465–474.
- ICALP-1996-AlonS #approximate #integer #parallel #problem #programming
- Improved Parallel Approximation of a Class of Integer Programming Programming Problems (NA, AS), pp. 562–573.
- STOC-1996-AlonMS #approximate #complexity
- The Space Complexity of Approximating the Frequency Moments (NA, YM, MS), pp. 20–29.
- STOC-1994-AlonK #graph #random
- A spectral technique for coloring random 3-colorable graphs (NA, NK), pp. 346–355.
- STOC-1994-AlonYZ #graph #named #scalability
- Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (NA, RY, UZ), pp. 326–335.
- STOC-1993-AlonCG #graph #permutation
- Routing permutations on graphs via matchings (NA, FRKC, RLG), pp. 583–591.
- STOC-1990-AlonST #graph #theorem
- A Separator Theorem for Graphs with an Excluded Minor and its Applications (NA, PDS, RT), pp. 293–299.
- STOC-1989-AlonBLP #communication #complexity #on the
- On the Complexity of Radio Communication (NA, ABN, NL, DP), pp. 274–285.
- STOC-1985-Alon #sorting
- Expanders, Sorting in Rounds and Superconcentrators of Limited Depth (NA), pp. 98–102.