×

zbMATH — the first resource for mathematics

Linial, Nathan

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

Co-Authors

15 single-authored
19 Saks, Michael E.
8 Naor, Assaf
7 Meshulam, Roy
6 Bartal, Yair
6 Hoory, Shlomo
6 Magen, Avner
6 Matoušek, Jiří
6 Mendel, Manor
6 Peled, Yuval
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 Nowik, Tahl
4 Peleg, David
4 Samorodnitsky, Alex
4 Shraibman, Adi
3 Aharoni, Ron
3 Aronshtam, Lior
3 Daniely, Amit
3 Dolev, Danny
3 Hass, Joel
3 Kushilevitz, Eyal
3 Morgenstern, Avraham
3 Rozenman, Eyal
3 Sudakov, Benny
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 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 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 Dotan, M.
1 Drier, Yotam
1 El-Yaniv, Ran
1 Ellis, David Christopher
1 Feitelson, Dror G.
1 Friedman, Joel
1 Furedi, Zoltan
1 Goldreich, Oded
1 Goldwasser, Shafi
1 Grant, Douglas D.
1 Halpern, Joseph Yehuda
1 Holzmann, Ron
1 Huang, Hao
1 Jaeger, François
1 Kaniel, Ron
1 Katznelson, Yitzhak
1 Khanna, Sanjeev
1 Klawe, Maria Margaret
1 Krauthgamer, Robert
1 Kupferman, Raz
1 Lehrer, Ehud
1 Lipson, Doron
1 Louis, Sria
1 Lovász, László
1 Łuczak, Tomasz
...and 20 more Co-Authors

Publications by Year

Citations contained in zbMATH

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

Cited by 2,548 Authors

48 Linial, Nathan
39 Naor, Assaf
28 Lai, Hong-Jian
25 Li, Xiangwen
21 Pelc, Andrzej
18 Alon, Noga M.
15 Lee, James R.
14 Barvinok, Alexander I.
14 Fraigniaud, Pierre
14 Mendel, Manor
14 Neiman, Ofer
14 Sudakov, Benny
13 Peleg, David
13 Saks, Michael E.
12 Bartal, Yair
12 Elkin, Michael
11 Kowalski, Dariusz R.
11 Mossel, Elchanan
11 Servedio, Rocco A.
11 Suomela, Jukka
10 Cioabă, Sebastian M.
10 Farber, Michael S.
10 Kahle, Matthew
10 Keller, Nathan
10 Matoušek, Jiří
10 Meshulam, Roy
10 Wigderson, Avi
10 Zuckerman, David
9 Bolla, Marianna
9 Costa, Armindo
9 Gąsieniec, Leszek Antoni
9 Gavoille, Cyril
9 Kranakis, Evangelos Konstantinou
9 Li, Jiaao
9 Zemmari, Akka
8 Cicalese, Ferdinando
8 Kalai, Gil
8 Kleine Büning, Hans
8 Luo, Rong
8 O’Donnell, Ryan
8 Peres, Yuval
8 Puder, Doron
8 Xu, Rui
8 Yeo, Anders
8 Zhang, Cunquan
7 Feige, Uriel
7 Flammini, Michele
7 Gurvich, Vladimir A.
7 Gutin, Gregory Z.
7 Lubotzky, Alexander
7 Métivier, Yves
7 Robson, John Michael
7 Samorodnitsky, Alex
7 Srinivasan, Aravind
7 Wattenhofer, Roger P.
7 Xu, Weijun
7 Yin, Jianhua
6 Barenboim, Leonid
6 Benjamini, Itai
6 Bollobás, Béla
6 Brightwell, Graham R.
6 Esperet, Louis
6 Even-Zohar, Chaim
6 Hartman, Irith Ben-Arroyo
6 Hoory, Shlomo
6 Lubetzky, Eyal
6 Mohar, Bojan
6 Nešetřil, Jaroslav
6 Novik, Isabella
6 Parzanchevski, Ori
6 Peled, Yuval
6 Rabinovich, Yuri
6 Rajsbaum, Sergio
6 Ron, Dana
6 Rubinfeld, Ronitt
6 Shao, Yehong
6 Szeider, Stefan
6 Yehudayoff, Amir
6 Zhang, Weiguo
6 Zhao, Xishun
5 Abajo, E.
5 Amano, Kazuyuki
5 Borodin, Allan B.
5 Boros, Endre
5 Bshouty, Nader H.
5 Censor-Hillel, Keren
5 Chandran, L. Sunil
5 DeVos, Matthew
5 Diánez, Ana
5 Dragan, Feodor F.
5 Duminil-Copin, Hugo
5 Emek, Yuval
5 Fox, Jacob
5 Göös, Mika
5 Han, Miaomiao
5 Hou, Xinmin
5 Khot, Subhash Ajit
5 Král’, Daniel
5 Krivelevich, Michael
5 Kullmann, Oliver
...and 2,448 more Authors
all top 5

Cited in 278 Serials

141 Theoretical Computer Science
92 Discrete Mathematics
84 Discrete Applied Mathematics
53 Distributed Computing
50 Journal of Computer and System Sciences
45 Algorithmica
44 Information Processing Letters
43 European Journal of Combinatorics
43 Combinatorica
41 Discrete & Computational Geometry
40 Graphs and Combinatorics
39 Journal of Combinatorial Theory. Series B
38 SIAM Journal on Computing
35 Random Structures & Algorithms
34 Combinatorics, Probability and Computing
31 Israel Journal of Mathematics
31 Information and Computation
31 SIAM Journal on Discrete Mathematics
30 Computational Complexity
27 Linear Algebra and its Applications
26 Journal of Combinatorial Theory. Series A
25 Theory of Computing Systems
22 Journal of Graph Theory
15 Mathematical Programming. Series A. Series B
14 Advances in Mathematics
14 Annals of Mathematics. Second Series
13 Geometric and Functional Analysis. GAFA
13 The Electronic Journal of Combinatorics
12 The Annals of Probability
12 Probability Theory and Related Fields
11 Journal of Combinatorial Optimization
10 Linear and Multilinear Algebra
10 Order
9 Proceedings of the American Mathematical Society
9 Transactions of the American Mathematical Society
9 Journal of Topology and Analysis
8 Topology and its Applications
8 Journal of the American Mathematical Society
8 Designs, Codes and Cryptography
8 Bulletin of the American Mathematical Society. New Series
8 Journal of the European Mathematical Society (JEMS)
8 Journal of Discrete Algorithms
7 Inventiones Mathematicae
7 Networks
7 Advances in Applied Mathematics
7 The Annals of Applied Probability
7 Computational Geometry
7 Journal of Physics A: Mathematical and Theoretical
6 Communications in Mathematical Physics
6 Journal of Mathematical Analysis and Applications
6 Duke Mathematical Journal
6 Operations Research Letters
6 Games and Economic Behavior
6 Experimental Mathematics
6 Journal of Algebraic Combinatorics
6 Foundations of Computational Mathematics
5 Geometriae Dedicata
5 Journal of Functional Analysis
5 Journal of Machine Learning Research (JMLR)
5 Discrete Mathematics, Algorithms and Applications
4 Artificial Intelligence
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 Journal of Global Optimization
4 Journal of Mathematical Sciences (New York)
4 Journal of the ACM
4 Acta Mathematica Sinica. English Series
4 Forum of Mathematics, Sigma
4 Computer Science Review
4 Journal of Applied and Computational Topology
3 Bulletin of the Australian Mathematical Society
3 Problems of Information Transmission
3 Mathematics of Computation
3 Publications Mathématiques
3 Mathematical Systems Theory
3 Acta Mathematicae Applicatae Sinica. English Series
3 Applied Mathematics Letters
3 Journal of Cryptology
3 Annals of Operations Research
3 Machine Learning
3 International Journal of Foundations of Computer Science
3 European Journal of Operational Research
3 International Journal of Computer Mathematics
3 Proceedings of the National Academy of Sciences of the United States of America
3 Stochastic Processes and their Applications
3 Calculus of Variations and Partial Differential Equations
3 Annals of Mathematics and Artificial Intelligence
3 Annals of Combinatorics
3 Frontiers of Mathematics in China
3 Japanese Journal of Mathematics. 3rd Series
2 Computers & Mathematics with Applications
2 Journal of Mathematical Physics
2 Journal of Statistical Physics
2 Mathematical Proceedings of the Cambridge Philosophical Society
2 Acta Mathematica
2 Acta Mathematica Vietnamica
2 Information Sciences
...and 178 more Serials
all top 5

Cited in 51 Fields

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

Citations by Year

Wikidata Timeline

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