default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDNathan Linial
Nati Linial
Person information
- affiliation: Hebrew University of Jerusalem, Israel
- award (2013): Dijkstra Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j142]Asaf Etgar, Nati Linial:
On the connectivity and diameter of geodetic graphs. Eur. J. Comb. 116: 103886 (2024)- [i22]Gal Beniamini, Nati Linial, Adi Shraibman:
The Rank-Ramsey Problem and the Log-Rank Conjecture. CoRR abs/2405.07337 (2024) - 2023
- [j141]Amir Dahari
, Nathan Linial:
In Search of Hyperpaths. Discret. Comput. Geom. 69(2): 399-421 (2023) - [j140]Daniel Cizma, Nati Linial:
Irreducible nonmetrizable path systems in graphs. J. Graph Theory 102(1): 5-14 (2023) - [j139]Elyassaf Loyfer, Nati Linial:
New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes. IEEE Trans. Inf. Theory 69(5): 2886-2899 (2023) - [i21]Nati Linial, Elyassaf Loyfer:
An Elementary Proof of the First LP Bound on the Rate of Binary Codes. CoRR abs/2303.16619 (2023) - 2022
- [j138]Shoni Gilboa, Roman Glebov, Dan Hefetz, Nati Linial, Avraham Morgenstern:
On the Local Structure of Oriented Graphs - a Case Study in Flag Algebras. Electron. J. Comb. 29(3) (2022) - [j137]Daniel Cizma, Nati Linial:
Geodesic Geometry on Graphs. Discret. Comput. Geom. 68(1): 298-347 (2022) - [i20]Nati Linial, Idan Orzech:
Bounds on Unique-Neighbor Codes. CoRR abs/2203.10330 (2022) - [i19]Elyassaf Loyfer, Nati Linial:
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes. CoRR abs/2206.09211 (2022) - [i18]Elyassaf Loyfer, Nati Linial:
Linear Programming Hierarchies in Coding Theory: Dual Solutions. CoRR abs/2211.12977 (2022) - 2021
- [j136]Nati Linial, Michael Simkin:
A randomized construction of high girth regular graphs. Random Struct. Algorithms 58(2): 345-369 (2021) - [c56]Nati Linial, Adi Shraibman:
An Improved Protocol for the Exactly-N Problem. CCC 2021: 2:1-2:8 - 2020
- [j135]Michael Chapman, Nati Linial, Yuval Peled:
Expander Graphs - Both Local and Global. Comb. 40(4): 473-509 (2020) - [j134]Nathan Linial, Sria Louis:
Asymptotically Almost Every 2r-Regular Graph Has an Internal Partition. Graphs Comb. 36(1): 41-50 (2020) - [j133]Nati Linial, Jonathan Mosheiff:
On the weight distribution of random binary linear codes. Random Struct. Algorithms 56(1): 5-36 (2020) - [c55]Nadav Brandes, Nathan Linial, Michal Linial:
Functional Evolutionary Modeling Exposes Overlooked Protein-Coding Genes Involved in Cancer. ISBRA 2020: 119-126 - [c54]Nadav Brandes, Nathan Linial, Michal Linial:
PWAS: Proteome-Wide Association Study. RECOMB 2020: 237-239 - [i17]Amir Dahari, Nati Linial:
Hyperpaths. CoRR abs/2011.09936 (2020)
2010 – 2019
- 2019
- [j132]Shelly Mahlab-Aviv, Nathan Linial, Michal Linial:
A cell-based probabilistic approach unveils the concerted action of miRNAs. PLoS Comput. Biol. 15(12) (2019) - [j131]Nati Linial, Yuval Peled:
Enumeration and randomized constructions of hypertrees. Random Struct. Algorithms 55(3): 677-695 (2019) - [c53]Michael Chapman, Nati Linial, Yuval Peled:
Expander Graphs - Both Local and Global. FOCS 2019: 158-170 - [c52]Nati Linial, Toniann Pitassi, Adi Shraibman:
On the Communication Complexity of High-Dimensional Permutations. ITCS 2019: 54:1-54:20 - [i16]Yehuda Afek, Eli Gafni, Nati Linial:
A King in every two consecutive tournaments. CoRR abs/1910.09684 (2019) - 2018
- [j130]Nathan Linial, Michael Simkin:
Monotone Subsequences in High-Dimensional Permutations. Comb. Probab. Comput. 27(1): 69-83 (2018) - [i15]Nati Linial, Jonathan Mosheiff:
On the weight distribution of random binary linear codes. CoRR abs/1806.08392 (2018) - 2017
- [j129]Nati Linial, Jonathan Mosheiff:
On the Rigidity of Sparse Random Graphs. J. Graph Theory 85(2): 466-480 (2017) - [i14]Nati Linial, Adi Shraibman:
On The Communication Complexity of High-Dimensional Permutations. CoRR abs/1706.02207 (2017) - 2016
- [j128]Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, Benny Sudakov:
On the densities of cliques and independent sets in graphs. Comb. 36(5): 493-512 (2016) - [j127]Chaim Even-Zohar, Joel Hass, Nati Linial, Tahl Nowik:
Invariants of Random Knots and Links. Discret. Comput. Geom. 56(2): 274-314 (2016) - [j126]Sébastien Bubeck, Nati Linial:
On the Local Profiles of Trees. J. Graph Theory 81(2): 109-119 (2016) - [j125]Amir Ban, Nati Linial:
Internal Partitions of Regular Graphs. J. Graph Theory 83(1): 5-18 (2016) - [j124]Nati Linial, Avraham Morgenstern:
On the Number of 4-Cycles in a Tournament. J. Graph Theory 83(3): 266-276 (2016) - [j123]Lior Aronshtam, Nathan Linial:
The threshold for d-collapsibility in random complexes. Random Struct. Algorithms 48(2): 260-269 (2016) - 2015
- [j122]Chaim Even-Zohar, Nati Linial:
A Note on the Inducibility of 4-Vertex Graphs. Graphs Comb. 31(5): 1367-1380 (2015) - [j121]Nati Linial, Avraham Morgenstern:
Graphs with Few 3-Cliques and 3-Anticliques are 3-Universal. J. Graph Theory 78(3): 229-238 (2015) - [j120]Chaim Even-Zohar, Nati Linial:
Triply Existentially Complete Triangle-Free Graphs. J. Graph Theory 78(4): 305-317 (2015) - [j119]Lior Aronshtam, Nathan Linial:
When does the top homology of a random simplicial complex vanish? Random Struct. Algorithms 46(1): 26-35 (2015) - [i13]Nati Linial, Jonathan Mosheiff:
On the Rigidity of Sparse Random Graphs. CoRR abs/1505.01189 (2015) - 2014
- [j118]Nadav Rappoport, Amos Stern, Nathan Linial, Michal Linial:
Entropy-driven partitioning of the hierarchical protein space. Bioinform. 30(17): 624-630 (2014) - [j117]Nathan Linial, Zur Luria:
An upper bound on the number of high-dimensional permutations. Comb. 34(4): 471-486 (2014) - [j116]David Ellis, Nathan Linial:
On Regular Hypergraphs of High Girth. Electron. J. Comb. 21(1): 1 (2014) - [j115]Nathan Linial, Zur Luria:
On the Vertices of the d-Dimensional Birkhoff Polytope. Discret. Comput. Geom. 51(1): 161-170 (2014) - [j114]Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, Benny Sudakov:
On the 3-Local Profiles of Graphs. J. Graph Theory 76(3): 236-248 (2014) - [j113]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Musical Chairs. SIAM J. Discret. Math. 28(3): 1578-1600 (2014) - [c51]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
The Complexity of Learning Halfspaces using Generalized Linear Methods. COLT 2014: 244-286 - [c50]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
From average case complexity to improper learning complexity. STOC 2014: 441-448 - [i12]Amir Ban, Nati Linial:
Market Share Indicates Quality. CoRR abs/1407.3641 (2014) - 2013
- [j112]Lior Aronshtam, Nathan Linial, Tomasz Luczak, Roy Meshulam:
Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes. Discret. Comput. Geom. 49(2): 317-334 (2013) - [j111]Nati Linial, Avraham Morgenstern:
On High-Dimensional Acyclic Tournaments. Discret. Comput. Geom. 50(4): 1085-1100 (2013) - [j110]Nathan Linial, Zur Luria:
An upper bound on the number of Steiner triple systems. Random Struct. Algorithms 43(4): 399-406 (2013) - [c49]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
More data speeds up training time in learning halfspaces over sparse vectors. NIPS 2013: 145-153 - [c48]Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks:
On the practically interesting instances of MAXCUT. STACS 2013: 526-537 - [i11]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
More data speeds up training time in learning halfspaces over sparse vectors. CoRR abs/1311.2271 (2013) - [i10]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
From average case complexity to improper learning complexity. CoRR abs/1311.2272 (2013) - 2012
- [j109]Yonatan Bilu, Nathan Linial:
Are Stable Instances Easy? Comb. Probab. Comput. 21(5): 643-660 (2012) - [j108]Nayantara Bhatnagar, Nathan Linial:
On the Lipschitz constant of the RSK correspondence. J. Comb. Theory A 119(1): 63-82 (2012) - [j107]Amir Ban, Nati Linial:
Strong convergence in posets. J. Comb. Theory A 119(6): 1299-1301 (2012) - [j106]Amit Daniely, Nathan Linial:
Tight products and graph expansion. J. Graph Theory 69(4): 426-440 (2012) - [j105]Nadav Rappoport, Solange Karsenty, Amos Stern, Nathan Linial, Michal Linial:
ProtoNet 6.0: organizing 10 million protein sequences in a compact hierarchical family tree. Nucleic Acids Res. 40(Database-Issue): 313-320 (2012) - [c47]Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, Nathan Linial:
No justified complaints: on fair sharing of multiple resources. ITCS 2012: 68-75 - [i9]Amit Daniely, Nati Linial, Michael E. Saks:
Clustering is difficult only when it does not matter. CoRR abs/1205.4891 (2012) - [i8]Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks:
On the practically interesting instances of MAXCUT. CoRR abs/1205.4893 (2012) - [i7]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Musical chairs. CoRR abs/1208.0813 (2012) - [i6]Amit Daniely, Nati Linial, Shai Shalev-Shwartz:
The error rate of learning halfspaces using Kernel-SVMs. CoRR abs/1211.0616 (2012) - 2011
- [j104]Yosef Prat, Menachem Fromer, Nathan Linial, Michal Linial:
Recovering key biological constituents through sparse representation of gene expression. Bioinform. 27(5): 655-661 (2011) - [j103]Regev Schweiger, Michal Linial, Nathan Linial:
Generative probabilistic models for protein-protein interaction networks - the biclique perspective. Bioinform. 27(13): 142-148 (2011) - [j102]Nathan Linial, Tahl Nowik:
The Expected Genus of a Random Chord Diagram. Discret. Comput. Geom. 45(1): 161-180 (2011) - [j101]Yael Dekel, James R. Lee, Nathan Linial:
Eigenvectors of random graphs: Nodal Domains. Random Struct. Algorithms 39(1): 39-58 (2011) - [c46]Yosef Prat, Menachem Fromer, Michal Linial, Nathan Linial:
Geometric Interpretation of Gene Expression by Sparse Reconstruction of Transcript Profiles. RECOMB 2011: 355-357 - [c45]Amir Ban, Nati Linial:
The dynamics of reputation systems. TARK 2011: 91-100 - [c44]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Oblivious Collaboration. DISC 2011: 489-504 - [i5]Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov:
Oblivious Collaboration. CoRR abs/1106.2065 (2011) - [i4]Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, Nati Linial:
No justified complaints: On fair sharing of multiple resources. CoRR abs/1106.2673 (2011) - 2010
- [j100]Nathan Linial, Roy Meshulam, M. Rosenthal:
Sum Complexes - a New Family of Hypertrees. Discret. Comput. Geom. 44(3): 622-636 (2010) - [j99]Nati Linial, Doron Puder:
Word maps and spectra of random graph lifts. Random Struct. Algorithms 37(1): 100-135 (2010) - [c43]Yonatan Bilu, Nathan Linial:
Are Stable Instances Easy? ICS 2010: 332-341 - [i3]Amit Daniely, Nathan Linial:
Tight products and Expansion. CoRR abs/1001.3661 (2010)
2000 – 2009
- 2009
- [j98]Nathan Linial, Adi Shraibman:
Learning Complexity vs Communication Complexity. Comb. Probab. Comput. 18(1-2): 227-245 (2009) - [j97]Nati Linial, Adi Shraibman:
Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms 34(3): 368-394 (2009) - [i2]Yonatan Bilu, Nathan Linial:
Are stable instances easy? CoRR abs/0906.3162 (2009) - [i1]Yonatan Bilu, Nathan Linial:
Are stable instances easy? Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j96]Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos:
Graph Colouring with No Large Monochromatic Components. Comb. Probab. Comput. 17(4): 577-589 (2008) - [c42]Nati Linial, Adi Shraibman:
Learning Complexity vs. Communication Complexity. CCC 2008: 53-63 - 2007
- [j95]Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman:
Complexity measures of sign matrices. Comb. 27(4): 439-463 (2007) - [j94]Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos:
Graph coloring with no large monochromatic components. Electron. Notes Discret. Math. 29: 115-122 (2007) - [j93]Elon Portugaly, Nathan Linial, Michal Linial:
EVEREST: a collection of evolutionary conserved protein domains. Nucleic Acids Res. 35(Database-Issue): 241-246 (2007) - [c41]Yael Dekel, James R. Lee, Nathan Linial:
Eigenvectors of Random Graphs: Nodal Domains. APPROX-RANDOM 2007: 436-448 - [c40]Nati Linial, Adi Shraibman:
Lower bounds in communication complexity based on factorization norms. STOC 2007: 699-708 - 2006
- [j92]Elon Portugaly, Amir Harel, Nathan Linial, Michal Linial:
EVEREST: automatic identification and classification of protein domains in all protein sequences. BMC Bioinform. 7: 277 (2006) - [j91]Nathan Linial, Roy Meshulam:
Homological Connectivity Of Random 2-Complexes. Comb. 26(4): 475-487 (2006) - [j90]Yonatan Bilu, Nathan Linial:
Lifts, Discrepancy and Nearly Optimal Spectral Gap*. Comb. 26(5): 495-519 (2006) - [j89]Nathan Linial, Michael E. Saks, David Statter:
The Non-Crossing Graph. Electron. J. Comb. 13(1) (2006) - [j88]Alon Amit, Nathan Linial:
Random Lifts of Graphs: Edge Expansion. Comb. Probab. Comput. 15(3): 317-332 (2006) - [j87]Nathan Linial, Isabella Novik:
How Neighborly Can a Centrally Symmetric Polytope Be? Discret. Comput. Geom. 36(2): 273-281 (2006) - [j86]Doron Lipson, Yonatan Aumann, Amir Ben-Dor, Nathan Linial, Zohar Yakhini:
Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis. J. Comput. Biol. 13(2): 215-228 (2006) - [j85]Nathan Linial, Eran London:
On the expansion rate of Margulis expanders. J. Comb. Theory B 96(3): 436-442 (2006) - [j84]Yotam Drier, Nathan Linial:
Minors in lifts of graphs. Random Struct. Algorithms 29(2): 208-225 (2006) - 2005
- [j83]Nathan Linial, Eyal Rozenman:
Random Lifts Of Graphs: Perfekt Matchings. Comb. 25(4): 407-424 (2005) - [j82]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
Some Low Distortion Metric Ramsey Problems. Discret. Comput. Geom. 33(1): 27-41 (2005) - [j81]Yonatan Bilu, Nathan Linial:
Monotone maps, sphericity and bounded second eigenvalue. J. Comb. Theory B 95(2): 283-299 (2005) - [j80]Shlomo Hoory, Nathan Linial:
A counterexample to a conjecture of Björner and Lovász on the chi-coloring complex. J. Comb. Theory B 95(2): 346-349 (2005) - [j79]Nathan Linial, Jaikumar Radhakrishnan:
Essential covers of the cube by hyperplanes. J. Comb. Theory A 109(2): 331-338 (2005) - [j78]Noam Kaplan, Ori Sasson, Uri Inbar, Moriah Friedlich, Menachem Fromer, Hillel Fleischer, Elon Portugaly, Nathan Linial, Michal Linial:
ProtoNet 4.0: A hierarchical classification of one million protein sequences. Nucleic Acids Res. 33(Database-Issue): 216-218 (2005) - [c39]Doron Lipson, Yonatan Aumann, Amir Ben-Dor, Nathan Linial, Zohar Yakhini:
Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis. RECOMB 2005: 83-100 - 2004
- [j77]Yonatan Bilu, Nathan Linial:
Ramanujan Signing of Regular Graphs. Comb. Probab. Comput. 13(6): 911-912 (2004) - [j76]Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jirí Matousek:
The One-Round Voronoi Game. Discret. Comput. Geom. 31(1): 125-138 (2004) - [j75]Robert Krauthgamer, Nathan Linial, Avner Magen:
Metric Embeddings--Beyond One-Dimensional Distortion. Discret. Comput. Geom. 31(3): 339-356 (2004) - [j74]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25(1): 87-92 (2004) - [j73]Shlomo Hoory, Nathan Linial:
Colorings of the d-regular infinite tree. J. Comb. Theory B 91(2): 161-167 (2004) - [c38]Yonatan Bilu, Nathan Linial:
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. FOCS 2004: 404-412 - 2003
- [j72]Nathan Linial, Michael E. Saks:
The Euclidean Distortion of Complete Binary Trees. Discret. Comput. Geom. 29(1): 19-21 (2003) - [j71]Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, Michal Linial:
ProtoNet: hierarchical classification of the protein space. Nucleic Acids Res. 31(1): 348-352 (2003) - [c37]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
On metric ramsey-type phenomena. STOC 2003: 463-472 - 2002
- [j70]Alon Amit, Nathan Linial:
Random Graph Coverings I: General Theory and Graph Connectivity. Comb. 22(1): 1-18 (2002) - [j69]Nathan Linial, Alex Samorodnitsky:
Linear Codes and Character Sums. Comb. 22(4): 497-522 (2002) - [j68]Noga Alon, Shlomo Hoory, Nathan Linial:
The Moore Bound for Irregular Graphs. Graphs Comb. 18(1): 53-57 (2002) - [j67]Nathan Linial, Eyal Rozenman:
An Extremal Problem on Degree Sequences of Graphs. Graphs Comb. 18(3): 573-582 (2002) - [j66]Alon Amit, Shlomo Hoory, Nathan Linial:
A Continuous Analogue of the Girth Problem. J. Comb. Theory B 84(2): 340-363 (2002) - [j65]Alon Amit, Nathan Linial, Jirí Matousek:
Random lifts of graphs: Independence and chromatic number. Random Struct. Algorithms 20(1): 1-22 (2002) - [c36]Nathan Linial:
Finite metric spaces: combinatorics, geometry and algorithms. SCG 2002: 63 - [c35]