×
Compute Distance To:
Author ID: linial.nathan Recent zbMATH articles by "Linial, Nathan"
Published as: Linial, Nathan; Linial, Nati; Linial, N.
Homepage: http://www.cs.huji.ac.il/~nati/
External Links: MGP · Wikidata · ResearchGate · dblp · GND
Documents Indexed: 172 Publications since 1976
Co-Authors: 124 Co-Authors with 157 Joint Publications
4,034 Co-Co-Authors
all top 5

Co-Authors

15 single-authored
19 Saks, Michael E.
8 Naor, Assaf
8 Peled, Yuval
7 Meshulam, Roy
6 Bartal, Yair
6 Hoory, Shlomo
6 Magen, Avner
6 Matoušek, Jiří
6 Mendel, Manor
6 Shraibman, Adi
6 Wigderson, Avi
5 Alon, Noga M.
5 Amit, Alon
5 Bar-Noy, Amotz
5 Bilu, Yonatan
5 Even-Zohar, Chaim
5 Nisan, Noam
5 Rabinovich, Yuri
5 Tarsi, Michael
4 Kahn, Jeff D.
4 Luria, Zur
4 Morgenstern, Avraham
4 Nowik, Tahl
4 Peleg, David
4 Samorodnitsky, Alex
4 Sudakov, Benny
3 Aharoni, Ron
3 Aronshtam, Lior
3 Daniely, Amit
3 Dolev, Danny
3 Hass, Joel
3 Kushilevitz, Eyal
3 Rozenman, Eyal
2 Afek, Yehuda
2 Awerbuch, Baruch
2 Babichenko, Yakov
2 Ban, Amir
2 Ben-Dor, Amir
2 Borodin, Allan B.
2 Cheong, Otfried
2 Cooper, Jason
2 Dekel, Yael
2 Erdős, Pál
2 Feige, Uriel
2 Gafni, Eli M.
2 Gotsman, Craig
2 Har-Peled, Sariel
2 Harari, Yuval
2 Huang, Hao
2 Kalai, Gil
2 Karchmer, Mauricio
2 Karlin, Anna R.
2 Lee, James R.
2 Lichtenstein, David
2 London, Eran
2 Luby, Michael G.
2 Mansour, Yishay
2 Mosheiff, Jonathan
2 Naves, Humberto
2 Newman, Ilan I.
2 Ostrovsky, Rafail
2 Parnas, Michal
2 Sasson, Ori
2 Sheffet, Or
2 Tardos, Gábor
2 Zuckerman, David
1 Aggarwal, Alok
1 Ajtai, Miklós
1 Andersen, Lars Døvling
1 Aumann, Yonatan
1 Azar, Yossi
1 Ben-Or, Michael
1 Bhatnagar, Nayantara
1 Birk, Yitzhak
1 Bourgain, Jean
1 Broder, Andrei Z.
1 Bubeck, Sébastien
1 Cizma, Daniel
1 Dotan, M.
1 Drier, Yotam
1 El-Yaniv, Ran
1 Ellis, David Christopher
1 Feitelson, Dror G.
1 Friedman, Joel
1 Furedi, Zoltan
1 Gilboa, Shoni
1 Glebov, Roman
1 Goldreich, Oded
1 Goldwasser, Shafi
1 Grant, Douglas D.
1 Halpern, Joseph Yehuda
1 Hefetz, Dan
1 Holzman, Ron
1 Jaeger, François
1 Kaniel, Ron
1 Katznelson, Yitzhak
1 Khanna, Sanjeev
1 Klawe, Maria Margaret
1 Krauthgamer, Robert
1 Kupferman, Raz
...and 24 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

156 Publications have been cited 2,736 times in 2,223 Documents Cited by Year
Expander graphs and their applications. Zbl 1147.68608
Hoory, Shlomo; Linial, Nathan; Widgerson, Avi
405
2006
Locality in distributed graph algorithms. Zbl 0787.05058
Linial, Nathan
160
1992
The geometry of graphs and some of its algorithmic applications. Zbl 0827.05021
Linial, Nathan; London, Eran; Rabinovich, Yuri
157
1995
Group connectivity of graphs — a nonhomogeneous analogue of nowhere-zero flow properties. Zbl 0824.05043
Jaeger, François; Linial, Nathan; Payan, Charles; Tarsi, Michael
109
1992
Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006
Linial, Nathan; Mansour, Yishay; Nisan, Noam
102
1993
Homological connectivity of random 2-complexes. Zbl 1121.55013
Linial, Nathan; Meshulam, Roy
94
2006
A lower bound for radio broadcast. Zbl 0753.68006
Alon, Noga; Bar-Noy, Amotz; Linial, Nathan; Peleg, David
61
1991
Lifts, discrepancy and nearly optimal spectral gap. Zbl 1121.05054
Bilu, Yonatan; Linial, Nathan
59
2006
The influence of variables in product spaces. Zbl 0771.60002
Bourgain, Jean; Kahn, Jeff; Kalai, Gil; Katznelson, Yitzhak; Linial, Nathan
54
1992
An optimal on-line algorithm for metrical task system. Zbl 0799.68035
Borodin, Allan; Linial, Nathan; Saks, Michael E.
50
1992
The Moore bound for irregular graphs. Zbl 0990.05075
Alon, Noga; Hoory, Shlomo; Linial, Nathan
48
2002
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Zbl 0973.15004
Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi
46
2000
Hard enumeration problems in geometry and combinatorics. Zbl 0596.68041
Linial, Nathan
42
1986
On metric Ramsey-type phenomena. Zbl 1114.46007
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
41
2005
Low diameter graph decompositions. Zbl 0790.05067
Linial, Nathan; Saks, Michael
39
1993
Approximate inclusion-exclusion. Zbl 0738.05009
Linial, Nathan; Nisan, Noam
38
1990
Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. Zbl 0611.05045
Aharoni, Ron; Linial, Nathan
37
1986
Finite metric spaces—combinatorics, geometry and algorithms. Zbl 0997.05019
Linial, Nathan
30
2002
On the cover time of random walks on graphs. Zbl 0681.60064
Kahn, Jeff D.; Linial, Nathan; Nisan, Noam; Saks, Michael E.
29
1989
Collapsibility and vanishing of top homology in random simplicial complexes. Zbl 1260.05171
Aronshtam, Lior; Linial, Nathan; Łuczak, Tomasz; Meshulam, Roy
27
2013
The information-theoretic bound is good for merging. Zbl 0548.68065
Linial, Nathan
27
1984
Complexity measures of sign matrices. Zbl 1164.68006
Linial, Nati; Mendelson, Shahar; Schechtman, Gideon; Shraibman, Adi
25
2007
Combinatorial characterization of read-once formulae. Zbl 0781.06012
Karchmer, M.; Linial, N.; Newman, I.; Saks, M.; Wigderson, A.
24
1993
Random graph coverings. I: General theory and graph connectivity. Zbl 0996.05105
Amit, Alon; Linial, Nathan
23
2002
Girth and Euclidean distortion. Zbl 0991.05037
Linial, Nathan; Magen, Avner; Naor, Assaf
22
2002
Extending the Greene-Kleitman theorem to directed graphs. Zbl 0467.05029
Linial, Nathan
22
1981
Improved routing strategies with succinct tables. Zbl 0724.68004
Awerbuch, Baruch; Bar-Noy, Amotz; Linial, Nathan; Peleg, David
21
1990
Eigenvectors of random graphs: nodal domains. Zbl 1223.05275
Dekel, Yael; Lee, James R.; Linial, Nathan
20
2011
Word maps and spectra of random graph lifts. Zbl 1242.60011
Linial, Nati; Puder, Doron
20
2010
On the phase transition in random simplicial complexes. Zbl 1348.05193
Linial, Nathan; Peled, Yuval
20
2016
Rubber bands, convex embeddings and graph connectivity. Zbl 0674.05046
Linial, N.; Lovász, László; Wigderson, A.
19
1988
Competitive optimal on-line leasing. Zbl 0955.91024
El-Yaniv, R.; Kaniel, R.; Linial, N.
19
1999
Lower bounds in communication complexity based on factorization norms. Zbl 1202.94012
Linial, Nati; Shraibman, Adi
19
2009
Random lifts of graphs: edge expansion. Zbl 1095.05034
Amit, Alon; Linial, Nathan
19
2006
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
18
2000
Collective coin flipping and other models of imperfect randomness. Zbl 0675.90107
Ben Or, M.; Linial, N.; Saks, M.
18
1988
Invariants of random knots and links. Zbl 1354.57012
Even-Zohar, Chaim; Hass, Joel; Linial, Nati; Nowik, Tahl
18
2016
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 0886.68076
Linial, N.; Luby, M.; Saks, M.; Zuckerman, D.
17
1997
Additive bases of vector spaces over prime fields. Zbl 0739.11003
Alon, N.; Linial, N.; Meshulam, R.
17
1991
Searching ordered structures. Zbl 0578.68050
Linial, N.; Saks, M.
17
1985
Are stable instances easy? Zbl 1283.68153
Bilu, Yonatan; Linial, Nathan
17
2012
Random lifts of graphs: Independence and chromatic number. Zbl 0993.05071
Amit, Alon; Linial, Nathan; Matoušek, Jiří
16
2002
Learning complexity vs communication complexity. Zbl 1202.68314
Linial, Nati; Shraibman, Adi
16
2009
A lower bound for the circumference of a graph. Zbl 0344.05139
Linial, Nathan
16
1976
Legal coloring of graphs. Zbl 0598.05035
Linial, N.
16
1986
The one-round Voronoi game. Zbl 1079.91010
Cheong, Otfried; Har-Peled, Sariel; Linial, Nathan; Matoušek, Jiří
15
2004
Covering digraphs by paths. Zbl 0388.05038
Linial, Nathan
15
1978
Inclusion-exclusion: exact and approximate. Zbl 0881.68084
Kahn, J.; Linial, N.; Samorodnitsky, A.
15
1996
How neighborly can a centrally symmetric polytope be? Zbl 1127.52011
Linial, Nathan; Novik, Isabella
15
2006
An upper bound on the number of high-dimensional permutations. Zbl 1340.05007
Linial, Nathan; Luria, Zur
15
2014
An upper bound on the number of Steiner triple systems. Zbl 1278.05030
Linial, Nathan; Luria, Zur
15
2013
Random lifts of graphs: perfect matchings. Zbl 1091.05063
Linial, Nathan; Rozenman, Eyal
14
2005
Incidence matrices of subsets - a rank formula. Zbl 0499.05017
Linial, Nathan; Rothschild, Bruce L.
14
1981
A note on the inducibility of 4-vertex graphs. Zbl 1321.05143
Even-Zohar, Chaim; Linial, Nati
13
2015
Spectral properties of threshold functions. Zbl 0810.94040
Gotsman, Craig; Linial, Nathan
12
1994
When does the top homology of a random simplicial complex vanish? Zbl 1326.55019
Aronshtam, Lior; Linial, Nathan
12
2015
Largest digraphs contained in all n-tournaments. Zbl 0532.05032
Linial, N.; Saks, M.; Sós, Vera T.
11
1983
Internal partitions of regular graphs. Zbl 1346.05223
Ban, Amir; Linial, Nati
11
2016
Bounds on universal sequences. Zbl 0696.05035
Bar-Noy, Amotz; Borodin, Allan; Karchmer, Mauricio; Linial, Nathan; Werman, Michael
10
1989
Matroidal bijections between graphs. Zbl 0724.05067
Linial, Nathan; Meshulam, Roy; Tarsi, Michael
10
1988
The influence of large coalitions. Zbl 0807.90148
Ajtai, Miklós; Linial, Nathan
10
1993
Decomposing graphs into regions of small diameter. Zbl 0785.05073
Linial, Nathan; Saks, Michael
10
1991
On metric Ramsey-type phenomena. Zbl 1192.52025
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
10
2003
On the 3-local profiles of graphs. Zbl 1305.05120
Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny
10
2014
A deteministic strongly polynomial algorithm for matrix scaling and approximate permanents. Zbl 1027.68980
Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi
9
1998
Some low distortion metric Ramsey problems. Zbl 1069.05050
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
9
2005
Compact distributed data structures for adaptive routing. Zbl 0683.90095
Awerbuch, Baruch; Bar-Noy, Amotz; Linial, Nathan; Peleg, David
9
1989
Results on learnability and the Vapnik-Chervonenkis dimension. Zbl 0715.68071
Linial, Nathan; Mansour, Yishay; Rivest, Ronald L.
9
1991
The counterfeit coin problem revisited. Zbl 0486.68053
Linial, Nathan; Tarsi, Michael
9
1982
On the vertices of the \(d\)-dimensional Birkhoff polytope. Zbl 1284.05045
Linial, Nathan; Luria, Zur
9
2014
On the local profiles of trees. Zbl 1330.05037
Bubeck, Sébastien; Linial, Nati
9
2016
Some extremal problems arising from discrete control processes. Zbl 0699.90110
Lichtenstein, D.; Linial, N.; Saks, M.
8
1989
Balancing extensions via Brunn-Minkowski. Zbl 0735.06004
Kahn, Jeff; Linial, Nathan
8
1991
Every poset has a central element. Zbl 0582.06002
Linial, Nathan; Saks, Michael
8
1985
On the distance distribution of codes. Zbl 0831.94019
Kalai, Gil; Linial, Nathan
8
1995
From average case complexity to improper learning complexity. Zbl 1315.68164
Daniely, Amit; Linial, Nati; Shalev-Shwartz, Shai
8
2014
Monotone maps, sphericity and bounded second eigenvalue. Zbl 1077.05058
Bilu, Yonatan; Linial, Nati
7
2005
A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex. Zbl 1075.05036
Hoory, Shlomo; Linial, Nathan
7
2005
Game-theoretic aspects of computing. Zbl 0925.90092
Linial, Nathan
7
1994
On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels. Zbl 0825.94164
Birk, Yitzhak; Linial, Nathan; Meshulam, Roy
7
1993
Sum complexes—a new family of hypertrees. Zbl 1213.05038
Linial, N.; Meshulam, R.; Rosenthal, M.
7
2010
Graph colouring with no large monochronomatic components. Zbl 1171.05021
Linial, Nathan; Matoušek, Jiří; Sheffet, Or; Tardos, Gábor
7
2008
The threshold for \(d\)-collapsibility in random complexes. Zbl 1332.05158
Aronshtam, L.; Linial, N.
7
2016
Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders. Zbl 1026.05032
Linial, Nathan; Magen, Avner
6
2000
On convex body chasing. Zbl 0774.52008
Friedman, Joel; Linial, Nathan
6
1993
Single round simulation on radio networks. Zbl 0754.94024
Alon, Noga; Bar-Noy, Amotz; Linial, Nathan; Peleg, David
6
1992
The equivalence of two problems on the cube. Zbl 0769.05050
Gotsman, C.; Linial, N.
6
1992
Cycles of length 0 modulo k in directed graphs. Zbl 0629.05038
Alon, Noga; Linial, N.
6
1989
Minors in lifts of graphs. Zbl 1226.05235
Drier, Yotam; Linial, Nathan
6
2006
Graph coloring and monotone functions on posets. Zbl 0583.05027
Linial, Nathan
6
1986
Fast perfect-information leader-election protocols with linear immunity. Zbl 0833.68014
Cooper, Jason; Linial, Nathan
6
1995
Biased random walks. Zbl 0845.60071
Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Linial, Nathan; Phillips, Steven
6
1996
On the practically interesting instances of MAXCUT. Zbl 1354.68106
Bilu, Yonatan; Daniely, Amit; Linial, Nati; Saks, Michael
6
2013
Lower bounds in communication complexity based on factorization norms. Zbl 1232.68067
Linial, Nati; Shraibman, Adi
6
2007
No justified complaints: on fair sharing of multiple resources. Zbl 1348.91197
Dolev, Danny; Feitelson, Dror G.; Halpern, Joseph Y.; Kupferman, Raz; Linial, Nathan
6
2012
Fault-tolerant computation in the full information model. Zbl 0912.68037
Goldreich, Oded; Goldwasser, Shafi; Linial, Nathan
5
1998
Low dimensional embeddings of ultrametrics. Zbl 1042.54020
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
5
2004
Extremal \(k\)-colourable subgraphs. Zbl 0536.05029
Andersen, L. D.; Grant, D. D.; Linial, N.
5
1983
The expected genus of a random chord diagram. Zbl 1209.05066
Linial, Nathan; Nowik, Tahl
5
2011
Witness sets for families of binary vectors. Zbl 0840.68103
Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael
5
1996
Geodesic geometry on graphs. Zbl 1490.05130
Cizma, Daniel; Linial, Nati
1
2022
Larger corner-free sets from better NOF exactly-\(N\) protocols. Zbl 07471817
Linial, Nati; Shraibman, Adi
1
2021
Efficient, local and symmetric Markov chains that generate one-factorizations. Zbl 1463.05509
Dotan, M.; Linial, N.; Peled, Y.
2
2020
On the weight distribution of random binary linear codes. Zbl 1475.94193
Linial, Nati; Mosheiff, Jonathan
2
2020
Expander graphs – both local and global. Zbl 1474.05237
Chapman, Michael; Linial, Nati; Peled, Yuval
1
2020
Enumeration and randomized constructions of hypertrees. Zbl 1433.05340
Linial, Nati; Peled, Yuval
3
2019
Extremal hypercuts and shadows of simplicial complexes. Zbl 1410.05230
Linial, Nati; Newman, Ilan; Peled, Yuval; Rabinovich, Yuri
2
2019
Universal knot diagrams. Zbl 1440.57002
Even-Zohar, Chaim; Hass, Joel; Linial, Nati; Nowik, Tahl
2
2019
The distribution of knots in the Petaluma model. Zbl 1411.57012
Even-Zohar, Chaim; Hass, Joel; Linial, Nathan; Nowik, Tahl
3
2018
Monotone subsequences in high-dimensional permutations. Zbl 1378.05003
Linial, Nathan; Simkin, Michael
2
2018
Random simplicial complexes: around the phase transition. Zbl 1380.05205
Linial, Nathan; Peled, Yuval
4
2017
On the phase transition in random simplicial complexes. Zbl 1348.05193
Linial, Nathan; Peled, Yuval
20
2016
Invariants of random knots and links. Zbl 1354.57012
Even-Zohar, Chaim; Hass, Joel; Linial, Nati; Nowik, Tahl
18
2016
Internal partitions of regular graphs. Zbl 1346.05223
Ban, Amir; Linial, Nati
11
2016
On the local profiles of trees. Zbl 1330.05037
Bubeck, Sébastien; Linial, Nati
9
2016
The threshold for \(d\)-collapsibility in random complexes. Zbl 1332.05158
Aronshtam, L.; Linial, N.
7
2016
On the number of 4-cycles in a tournament. Zbl 1350.05051
Linial, Nati; Morgenstern, Avraham
5
2016
Discrepancy of high-dimensional permutations. Zbl 1346.05006
Linial, Nathan; Luria, Zur
3
2016
On the densities of cliques and independent sets in graphs. Zbl 07550000
Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny
1
2016
A note on the inducibility of 4-vertex graphs. Zbl 1321.05143
Even-Zohar, Chaim; Linial, Nati
13
2015
When does the top homology of a random simplicial complex vanish? Zbl 1326.55019
Aronshtam, Lior; Linial, Nathan
12
2015
Graphs with few 3-cliques and 3-anticliques are 3-universal. Zbl 1309.05138
Linial, Nati; Morgenstern, Avraham
3
2015
Triply existentially complete triangle-free graphs. Zbl 1309.05125
Even-Zohar, Chaim; Linial, Nati
2
2015
An upper bound on the number of high-dimensional permutations. Zbl 1340.05007
Linial, Nathan; Luria, Zur
15
2014
On the 3-local profiles of graphs. Zbl 1305.05120
Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny
10
2014
On the vertices of the \(d\)-dimensional Birkhoff polytope. Zbl 1284.05045
Linial, Nathan; Luria, Zur
9
2014
From average case complexity to improper learning complexity. Zbl 1315.68164
Daniely, Amit; Linial, Nati; Shalev-Shwartz, Shai
8
2014
On regular hypergraphs of high girth. Zbl 1300.05198
Ellis, David; Linial, Nathan
4
2014
Musical chairs. Zbl 1315.68265
Afek, Yehuda; Babichenko, Yakov; Feige, Uriel; Gafni, Eli; Linial, Nati; Sudakov, Benny
1
2014
Collapsibility and vanishing of top homology in random simplicial complexes. Zbl 1260.05171
Aronshtam, Lior; Linial, Nathan; Łuczak, Tomasz; Meshulam, Roy
27
2013
An upper bound on the number of Steiner triple systems. Zbl 1278.05030
Linial, Nathan; Luria, Zur
15
2013
On the practically interesting instances of MAXCUT. Zbl 1354.68106
Bilu, Yonatan; Daniely, Amit; Linial, Nati; Saks, Michael
6
2013
On high-dimensional acyclic tournaments. Zbl 1280.05052
Linial, Nati; Morgenstern, Avraham
4
2013
Are stable instances easy? Zbl 1283.68153
Bilu, Yonatan; Linial, Nathan
17
2012
No justified complaints: on fair sharing of multiple resources. Zbl 1348.91197
Dolev, Danny; Feitelson, Dror G.; Halpern, Joseph Y.; Kupferman, Raz; Linial, Nathan
6
2012
Tight products and graph expansion. Zbl 1242.05230
Daniely, Amit; Linial, Nathan
2
2012
Eigenvectors of random graphs: nodal domains. Zbl 1223.05275
Dekel, Yael; Lee, James R.; Linial, Nathan
20
2011
The expected genus of a random chord diagram. Zbl 1209.05066
Linial, Nathan; Nowik, Tahl
5
2011
Oblivious collaboration. Zbl 1350.68037
Afek, Yehuda; Babichenko, Yakov; Feige, Uriel; Gafni, Eli; Linial, Nati; Sudakov, Benny
2
2011
Word maps and spectra of random graph lifts. Zbl 1242.60011
Linial, Nati; Puder, Doron
20
2010
Sum complexes—a new family of hypertrees. Zbl 1213.05038
Linial, N.; Meshulam, R.; Rosenthal, M.
7
2010
Lower bounds in communication complexity based on factorization norms. Zbl 1202.94012
Linial, Nati; Shraibman, Adi
19
2009
Learning complexity vs communication complexity. Zbl 1202.68314
Linial, Nati; Shraibman, Adi
16
2009
Graph colouring with no large monochronomatic components. Zbl 1171.05021
Linial, Nathan; Matoušek, Jiří; Sheffet, Or; Tardos, Gábor
7
2008
Complexity measures of sign matrices. Zbl 1164.68006
Linial, Nati; Mendelson, Shahar; Schechtman, Gideon; Shraibman, Adi
25
2007
Lower bounds in communication complexity based on factorization norms. Zbl 1232.68067
Linial, Nati; Shraibman, Adi
6
2007
Graph coloring with no large monochromatic components. Zbl 1341.05080
Linial, Nathan; Matoušek, Jiří; Sheffet, Or; Tardos, Gábor
4
2007
Eigenvectors of random graphs: Nodal domains. Zbl 1171.05418
Dekel, Yael; Lee, James R.; Linial, Nathan
3
2007
Expander graphs and their applications. Zbl 1147.68608
Hoory, Shlomo; Linial, Nathan; Widgerson, Avi
405
2006
Homological connectivity of random 2-complexes. Zbl 1121.55013
Linial, Nathan; Meshulam, Roy
94
2006
Lifts, discrepancy and nearly optimal spectral gap. Zbl 1121.05054
Bilu, Yonatan; Linial, Nathan
59
2006
Random lifts of graphs: edge expansion. Zbl 1095.05034
Amit, Alon; Linial, Nathan
19
2006
How neighborly can a centrally symmetric polytope be? Zbl 1127.52011
Linial, Nathan; Novik, Isabella
15
2006
Minors in lifts of graphs. Zbl 1226.05235
Drier, Yotam; Linial, Nathan
6
2006
Limitations to Fréchet’s metric embedding method. Zbl 1132.46045
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
3
2006
On the expansion rate of Margulis expanders. Zbl 1089.05071
Linial, Nathan; London, Eran
1
2006
On metric Ramsey-type phenomena. Zbl 1114.46007
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
41
2005
Random lifts of graphs: perfect matchings. Zbl 1091.05063
Linial, Nathan; Rozenman, Eyal
14
2005
Some low distortion metric Ramsey problems. Zbl 1069.05050
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
9
2005
Monotone maps, sphericity and bounded second eigenvalue. Zbl 1077.05058
Bilu, Yonatan; Linial, Nati
7
2005
A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex. Zbl 1075.05036
Hoory, Shlomo; Linial, Nathan
7
2005
Essential covers of the cube by hyperplanes. Zbl 1066.52020
Linial, Nathan; Radhakrishnan, Jaikumar
5
2005
On metric Ramsey-type dichotomies. Zbl 1066.05142
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
4
2005
Efficient calculation of interval scores for DNA copy number data analysis. Zbl 1119.92325
Lipson, Doron; Aumann, Yonatan; Ben-Dor, Amir; Linial, Nathan; Yakhini, Zohar
2
2005
The one-round Voronoi game. Zbl 1079.91010
Cheong, Otfried; Har-Peled, Sariel; Linial, Nathan; Matoušek, Jiří
15
2004
Low dimensional embeddings of ultrametrics. Zbl 1042.54020
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
5
2004
Metric embeddings – beyond one-dimensional distortion. Zbl 1095.68086
Krauthgamer, Robert; Linial, Nathan; Magen, Avner
3
2004
Colorings of the \(d\)-regular infinite tree. Zbl 1048.05035
Hoory, Shlomo; Linial, Nathan
1
2004
On metric Ramsey-type phenomena. Zbl 1192.52025
Bartal, Yair; Linial, Nathan; Mendel, Manor; Naor, Assaf
10
2003
The Euclidean distortion of complete binary trees. Zbl 1008.05040
Linial, Nathan; Saks, Michael
4
2003
The Moore bound for irregular graphs. Zbl 0990.05075
Alon, Noga; Hoory, Shlomo; Linial, Nathan
48
2002
Finite metric spaces—combinatorics, geometry and algorithms. Zbl 0997.05019
Linial, Nathan
30
2002
Random graph coverings. I: General theory and graph connectivity. Zbl 0996.05105
Amit, Alon; Linial, Nathan
23
2002
Girth and Euclidean distortion. Zbl 0991.05037
Linial, Nathan; Magen, Avner; Naor, Assaf
22
2002
Random lifts of graphs: Independence and chromatic number. Zbl 0993.05071
Amit, Alon; Linial, Nathan; Matoušek, Jiří
16
2002
The one-round Voronoi game. Zbl 1415.91007
Cheong, Otfried; Har-Peled, Sariel; Linial, Nathan; Matoušek, Jiří
4
2002
An extremal problem on degree sequences of graphs. Zbl 1009.05045
Linial, Nathan; Rozenman, Eyal
3
2002
Linear codes and character sums. Zbl 1026.94024
Linial, Nathan; Samorodnitsky, Alex
3
2002
A continuous analogue of the girth problem. Zbl 1025.05041
Amit, Alon; Hoory, Shlomo; Linial, Nathan
1
2002
Girth and Euclidean distortion. Zbl 1192.05040
Linial, Nathan; Magen, Avner; Naor, Assaf
1
2002
Random lifts of graphs. Zbl 0986.05090
Amit, Alon; Linial, Nathan; Matoušek, Jiří; Rozenman, Eyal
3
2001
Neighborhood preserving hashing and approximate queries. Zbl 0992.68051
Dolev, Danny; Harari, Yuval; Linial, Nathan; Nisan, Noam; Parnas, Michal
1
2001
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Zbl 0973.15004
Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi
46
2000
On the hardness of approximating the chromatic number. Zbl 0964.68065
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel
18
2000
Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders. Zbl 1026.05032
Linial, Nathan; Magen, Avner
6
2000
Competitive optimal on-line leasing. Zbl 0955.91024
El-Yaniv, R.; Kaniel, R.; Linial, N.
19
1999
The linear-array conjecture in communication complexity is false. Zbl 0929.68129
Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail
4
1999
A deteministic strongly polynomial algorithm for matrix scaling and approximate permanents. Zbl 1027.68980
Linial, Nathan; Samorodnitsky, Alex; Wigderson, Avi
9
1998
Fault-tolerant computation in the full information model. Zbl 0912.68037
Goldreich, Oded; Goldwasser, Shafi; Linial, Nathan
5
1998
Trees and Euclidean metrics. Zbl 1029.68952
Linial, Nathan; Magen, Avner; Saks, Michael E.
2
1998
Low distortion Euclidean embeddings of trees. Zbl 0938.46017
Linial, Nathan; Magen, Avner; Saks, Michael E.
1
1998
Non-expansive hashing. Zbl 0926.68091
Linial, Nathan; Sasson, Ori
1
1998
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 0886.68076
Linial, N.; Luby, M.; Saks, M.; Zuckerman, D.
17
1997
Inclusion-exclusion: exact and approximate. Zbl 0881.68084
Kahn, J.; Linial, N.; Samorodnitsky, A.
15
1996
Biased random walks. Zbl 0845.60071
Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Linial, Nathan; Phillips, Steven
6
1996
Witness sets for families of binary vectors. Zbl 0840.68103
Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael
5
1996
Non-expansive hashing. Zbl 0922.68047
Linial, Nathan; Sasson, Ori
3
1996
The linear-array conjecture in communication complexity is false. Zbl 0932.94042
Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail
1
1996
The geometry of graphs and some of its algorithmic applications. Zbl 0827.05021
Linial, Nathan; London, Eran; Rabinovich, Yuri
157
1995
On the distance distribution of codes. Zbl 0831.94019
Kalai, Gil; Linial, Nathan
8
1995
...and 56 more Documents
all top 5

Cited by 3,029 Authors

55 Linial, Nathan
41 Naor, Assaf
30 Lai, Hong-Jian
25 Li, Xiangwen
22 Alon, Noga M.
21 Neiman, Ofer
21 Pelc, Andrzej
17 Lee, James R.
17 Sudakov, Benny
16 Suomela, Jukka
15 Barvinok, Alexander I.
15 Fraigniaud, Pierre
14 Bartal, Yair
14 Elkin, Michael
14 Mendel, Manor
14 Peleg, David
13 Farber, Michael S.
13 Kahle, Matthew
13 Saks, Michael E.
12 Kowalski, Dariusz R.
12 Mossel, Elchanan
12 Servedio, Rocco A.
11 Keller, Nathan
11 Li, Jiaao
11 Meshulam, Roy
11 Wigderson, Avi
11 Zuckerman, David
10 Bolla, Marianna
10 Gąsieniec, Leszek Antoni
10 Matoušek, Jiří
10 O’Donnell, Ryan
10 Peled, Yuval
9 Cioabă, Sebastian M.
9 Costa, Armindo
9 Esperet, Louis
9 Kleine Büning, Hans
9 Kranakis, Evangelos Konstantinou
9 Lubotzky, Alexander
9 Luo, Rong
9 Puder, Doron
9 Zhang, Cunquan
8 Cicalese, Ferdinando
8 Gavoille, Cyril
8 Kalai, Gil
8 Krivelevich, Michael
8 Peres, Yuval
8 Samorodnitsky, Alex
8 Xu, Rui
8 Yeo, Anders
8 Yin, Jianhua
8 Zemmari, Akka
8 Zhang, Yong
7 Barenboim, Leonid
7 Benjamini, Itai
7 Censor-Hillel, Keren
7 Even-Zohar, Chaim
7 Flammini, Michele
7 Gurvich, Vladimir A.
7 Gutin, Gregory Z.
7 Hatami, Hamed
7 Hirvonen, Juho
7 Lubetzky, Eyal
7 Métivier, Yves
7 Mohar, Bojan
7 Nešetřil, Jaroslav
7 Novik, Isabella
7 Pak, Igor
7 Parzanchevski, Ori
7 Pitassi, Toniann
7 Rabinovich, Yuri
7 Robson, John Michael
7 Ron, Dana
7 Shraibman, Adi
7 Srinivasan, Aravind
7 Szeider, Stefan
7 Wattenhofer, Roger P.
7 Xu, Weijun
6 Bollobás, Béla
6 Brightwell, Graham R.
6 DeVos, Matthew
6 Duminil-Copin, Hugo
6 Feige, Uriel
6 Filtser, Arnold
6 Goldreich, Oded
6 Hartman, Irith Ben-Arroyo
6 Hoory, Shlomo
6 Kahn, Jeff D.
6 Khot, Subhash Ajit
6 Král’, Daniel
6 Liu, Xiaogang
6 Mubayi, Dhruv
6 Rajsbaum, Sergio
6 Rubinfeld, Ronitt
6 Shao, Yehong
6 Sun, Xiaoming
6 Vu, Van H.
6 Wagner, Stephan G.
6 Yehudayoff, Amir
6 Zhang, Weiguo
6 Zhao, Xishun
...and 2,929 more Authors
all top 5

Cited in 315 Serials

144 Theoretical Computer Science
98 Discrete Mathematics
88 Discrete Applied Mathematics
59 Distributed Computing
55 Algorithmica
54 SIAM Journal on Computing
51 Combinatorica
51 Discrete & Computational Geometry
49 Journal of Computer and System Sciences
47 Journal of Combinatorial Theory. Series B
47 European Journal of Combinatorics
47 Graphs and Combinatorics
44 Information Processing Letters
38 The Electronic Journal of Combinatorics
36 SIAM Journal on Discrete Mathematics
35 Israel Journal of Mathematics
35 Random Structures & Algorithms
35 Combinatorics, Probability and Computing
34 Computational Complexity
33 Linear Algebra and its Applications
31 Information and Computation
26 Journal of Combinatorial Theory. Series A
26 Theory of Computing Systems
22 Journal of Graph Theory
17 Transactions of the American Mathematical Society
17 Mathematical Programming. Series A. Series B
16 Annals of Mathematics. Second Series
15 Advances in Mathematics
15 The Annals of Probability
15 Journal of Combinatorial Optimization
14 Probability Theory and Related Fields
13 Geometric and Functional Analysis. GAFA
12 Proceedings of the American Mathematical Society
11 Linear and Multilinear Algebra
11 Bulletin of the American Mathematical Society. New Series
10 Order
10 Journal of Topology and Analysis
9 The Annals of Applied Probability
9 Journal of the European Mathematical Society (JEMS)
8 Communications in Mathematical Physics
8 Duke Mathematical Journal
8 Topology and its Applications
8 Advances in Applied Mathematics
8 Journal of the American Mathematical Society
8 Machine Learning
8 Designs, Codes and Cryptography
8 Experimental Mathematics
8 Journal of Algebraic Combinatorics
8 Journal of Physics A: Mathematical and Theoretical
7 Inventiones Mathematicae
7 Networks
7 Computational Geometry
7 Journal of Discrete Algorithms
6 Journal of Mathematical Analysis and Applications
6 Journal of Functional Analysis
6 Operations Research Letters
6 Journal of Cryptology
6 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques
6 Foundations of Computational Mathematics
6 Journal of Machine Learning Research (JMLR)
5 Geometriae Dedicata
5 Acta Mathematica Hungarica
5 Games and Economic Behavior
5 Acta Mathematica Sinica. English Series
5 Discrete Mathematics, Algorithms and Applications
5 Forum of Mathematics, Sigma
5 Discrete Analysis
4 Applied Mathematics and Computation
4 Journal of Algebra
4 Mathematika
4 Journal of Theoretical Probability
4 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
4 International Journal of Foundations of Computer Science
4 Journal of Global Optimization
4 Stochastic Processes and their Applications
4 Journal of Knot Theory and its Ramifications
4 Applied and Computational Harmonic Analysis
4 Journal of Mathematical Sciences (New York)
4 Annals of Mathematics and Artificial Intelligence
4 Electronic Journal of Probability
4 Electronic Communications in Probability
4 Journal of the ACM
4 Cryptography and Communications
4 Computer Science Review
4 Journal of Applied and Computational Topology
4 Combinatorial Theory
3 Advances in Applied Probability
3 Artificial Intelligence
3 Bulletin of the Australian Mathematical Society
3 Physica A
3 Problems of Information Transmission
3 Mathematics of Computation
3 Publications Mathématiques
3 Journal of Optimization Theory and Applications
3 Mathematics of Operations Research
3 Mathematical Systems Theory
3 Operations Research
3 Acta Mathematicae Applicatae Sinica. English Series
3 Journal of Complexity
3 Applied Mathematics Letters
...and 215 more Serials
all top 5

Cited in 55 Fields

1,122 Combinatorics (05-XX)
939 Computer science (68-XX)
214 Probability theory and stochastic processes (60-XX)
169 Operations research, mathematical programming (90-XX)
169 Information and communication theory, circuits (94-XX)
115 Linear and multilinear algebra; matrix theory (15-XX)
101 Functional analysis (46-XX)
89 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
86 Group theory and generalizations (20-XX)
71 Convex and discrete geometry (52-XX)
69 Order, lattices, ordered algebraic structures (06-XX)
57 Algebraic topology (55-XX)
55 Number theory (11-XX)
47 Numerical analysis (65-XX)
45 Manifolds and cell complexes (57-XX)
44 Statistical mechanics, structure of matter (82-XX)
43 Mathematical logic and foundations (03-XX)
42 Quantum theory (81-XX)
36 Geometry (51-XX)
32 Statistics (62-XX)
29 General topology (54-XX)
27 Functions of a complex variable (30-XX)
19 Differential geometry (53-XX)
17 Biology and other natural sciences (92-XX)
16 Harmonic analysis on Euclidean spaces (42-XX)
14 Measure and integration (28-XX)
12 Algebraic geometry (14-XX)
12 Global analysis, analysis on manifolds (58-XX)
11 Commutative algebra (13-XX)
11 Topological groups, Lie groups (22-XX)
11 Operator theory (47-XX)
10 Dynamical systems and ergodic theory (37-XX)
9 Real functions (26-XX)
9 Partial differential equations (35-XX)
9 Calculus of variations and optimal control; optimization (49-XX)
8 Abstract harmonic analysis (43-XX)
7 Approximations and expansions (41-XX)
7 Systems theory; control (93-XX)
6 Ordinary differential equations (34-XX)
5 History and biography (01-XX)
4 General and overarching topics; collections (00-XX)
3 Field theory and polynomials (12-XX)
3 Category theory; homological algebra (18-XX)
2 General algebraic systems (08-XX)
2 Associative rings and algebras (16-XX)
2 Several complex variables and analytic spaces (32-XX)
2 Relativity and gravitational theory (83-XX)
1 Nonassociative rings and algebras (17-XX)
1 \(K\)-theory (19-XX)
1 Potential theory (31-XX)
1 Special functions (33-XX)
1 Difference and functional equations (39-XX)
1 Integral equations (45-XX)
1 Mechanics of particles and systems (70-XX)
1 Fluid mechanics (76-XX)

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.