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