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
- 2025
[j143]Gal Beniamini, Nir Lavee, Nati Linial:
How Balanced Can Permutations Be? Comb. 45(1): 9 (2025)- [i23]Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, Elyassaf Loyfer:
Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness. CoRR abs/2501.04854 (2025) - 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]Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jirí Matousek:
The one-round Voronoi game. SCG 2002: 97-101 - [c34]Ori Sasson, Nathan Linial, Michal Linial:
The metric space of proteins-comparative study of clustering algorithms. ISMB 2002: 14-21 - [c33]Nathan Linial, Avner Magen, Assaf Naor:
Girth and euclidean distortion. STOC 2002: 705-711 - 2001
- [j64]Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas:
Neighborhood Preserving Hashing and Approximate Queries. SIAM J. Discret. Math. 15(1): 73-85 (2001) - [c32]Alon Amit, Nathan Linial, Jirí Matousek, Eyal Rozenman:
Random lifts of graphs. SODA 2001: 883-894 - 2000
- [j63]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. Comb. 20(3): 393-415 (2000) - [j62]Nathan Linial, Alex Samorodnitsky, Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Comb. 20(4): 545-568 (2000) - [j61]Nathan Linial, Avner Magen:
Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders. J. Comb. Theory B 79(2): 157-171 (2000) - [j60]Golan Yona, Nathan Linial, Michal Linial:
ProtoMap: automatic classification of protein sequences and hierarchy of protein families. Nucleic Acids Res. 28(1): 49-55 (2000)
1990 – 1999
- 1999
- [j59]Ran El-Yaniv, Ron Kaniel, Nathan Linial:
Competitive Optimal On-Line Leasing. Algorithmica 25(1): 116-140 (1999) - [j58]Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky:
The Linear-Array Conjecture in Communication Complexity Is False. Comb. 19(2): 241-254 (1999) - [j57]Amir Ben-Dor, Anna R. Karlin, Nathan Linial, Yuri Rabinovich:
A Note on the Influence of an epsilon-Biased Random Source. J. Comput. Syst. Sci. 58(1): 174-176 (1999) - 1998
- [j56]Nathan Linial, Ori Sasson:
Non-Expansive Hashing. Comb. 18(1): 121-132 (1998) - [j55]Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-Tolerant Computation in the Full Information Model. SIAM J. Comput. 27(2): 506-544 (1998) - [c31]Golan Yona, Nathan Linial, Naftali Tishby, Michal Linial:
A Map of the Protein Space: An Automatic Hierarchical Classification of all Protein Sequences. ISMB 1998: 212-221 - [c30]Nathan Linial, Avner Magen, Michael E. Saks:
Trees and Euclidean Metrics. STOC 1998: 169-175 - [c29]Nathan Linial, Alex Samorodnitsky, Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652 - 1997
- [j54]Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Comb. 17(2): 215-234 (1997) - 1996
- [j53]Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips:
Biased Random Walks. Comb. 16(1): 1-18 (1996) - [j52]Jeff Kahn, Nathan Linial, Alex Samorodnitsky:
Inclusion-Exclusion: Exact and Approximate. Comb. 16(4): 465-477 (1996) - [j51]Shlomo Hoory, Nathan Linial:
Central Points for Sets in Rn (or: the Chocolate Ice-Cream Problem). Discret. Comput. Geom. 15(4): 467-479 (1996) - [j50]Eyal Kushilevitz, Nathan Linial, Yuri Rabinovich, Michael E. Saks:
Witness Sets for Families of Binary Vectors. J. Comb. Theory A 73(2): 376-380 (1996) - [c28]Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky:
The Linear-Array Conjecture in Communication Complexity is False. STOC 1996: 1-10 - [c27]Nathan Linial, Ori Sasson:
Non-Expansive Hashing. STOC 1996: 509-518 - 1995
- [j49]Nathan Linial, Eran London, Yuri Rabinovich:
The Geometry of Graphs and Some of its Algorithmic Applications. Comb. 15(2): 215-245 (1995) - [j48]Jason Cooper, Nathan Linial:
Fast Perfect-Information Leader-Election Protocols with Linear Immunity. Comb. 15(3): 319-332 (1995) - [j47]Gil Kalai, Nathan Linial:
On the distance distribution of codes. IEEE Trans. Inf. Theory 41(5): 1467-1472 (1995) - 1994
- [j46]Craig Gotsman, Nathan Linial:
Spectral Properties of Threshold Functions. Comb. 14(1): 35-50 (1994) - [j45]Nathan Linial, Yuri Rabinovich:
Local and Global Clique Numbers. J. Comb. Theory B 61(1): 5-15 (1994) - [c26]Nathan Linial, Eran London, Yuri Rabinovich:
The geometry of graphs and some of its algorithmic applications. FOCS 1994: 577-591 - [c25]Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas:
Neighborhood Preserving Hashing and Approximate Queries. SODA 1994: 251-259 - 1993
- [j44]Miklós Ajtai, Nathan Linial:
The influence of large coalitions. Comb. 13(2): 129-145 (1993) - [j43]Nathan Linial, Michael E. Saks:
Low diameter graph decompositions. Comb. 13(4): 441-454 (1993) - [j42]Nathan Linial:
Local-Global Phenomena in Graphs. Comb. Probab. Comput. 2: 491-503 (1993) - [j41]Joel Friedman, Nathan Linial:
On Convex Body Chasing. Discret. Comput. Geom. 9: 293-321 (1993) - [j40]Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson:
Combinatorial characterization of read-once formulae. Discret. Math. 114(1-3): 275-282 (1993) - [j39]Nathan Linial, Yishay Mansour, Noam Nisan:
Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM 40(3): 607-620 (1993) - [j38]Yitzhak Birk, Nathan Linial, Roy Meshulam:
On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels. IEEE Trans. Inf. Theory 39(1): 186-191 (1993) - [c24]Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks:
Sphere Packing and Local Majorities in Graphs. ISTCS 1993: 141-149 - [c23]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260 - [c22]Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267 - [c21]Jason Cooper, Nathan Linial:
Fast perfection-information leader-election protocol with linear immunity. STOC 1993: 662-671 - 1992
- [j37]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992) - [j36]Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
Single Round Simulation on Radio Networks. J. Algorithms 13(2): 188-210 (1992) - [j35]François Jaeger, Nathan Linial, Charles Payan, Michael Tarsi:
Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties. J. Comb. Theory B 56(2): 165-182 (1992) - [j34]Craig Gotsman, Nathan Linial:
The Equivalence of Two Problems on the Cube. J. Comb. Theory A 61(1): 142-146 (1992) - [j33]Nathan Linial:
Locality in Distributed Graph Algorithms. SIAM J. Comput. 21(1): 193-201 (1992) - [c20]Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips:
Biased Random Walks. STOC 1992: 1-9 - 1991
- [j32]Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson:
A Lower Bound on the Area of Permutation Layouts. Algorithmica 6(2): 241-255 (1991) - [j31]Jeff Kahn, Nathan Linial:
Balancing extensions via Brunn-Minkowski. Comb. 11(4): 363-368 (1991) - [j30]Nathan Linial, Yishay Mansour, Ronald L. Rivest:
Results on Learnability and the Vapnik-Chervonenkis Dimension. Inf. Comput. 90(1): 33-49 (1991) - [j29]Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
A Lower Bound for Radio Broadcast. J. Comput. Syst. Sci. 43(2): 290-298 (1991) - [j28]Noga Alon, Nathan Linial, Roy Meshulam:
Additive bases of vector spaces over prime fields. J. Comb. Theory A 57(2): 203-210 (1991) - [c19]Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-tolerant Computation in the Full Information Model (Extended Abstract). FOCS 1991: 447-457 - [c18]Nathan Linial, Michael E. Saks:
Decomposing Graphs into Regions of Small Diameter. SODA 1991: 320-330 - 1990
- [j27]Nathan Linial, Noam Nisan:
Approximate inclusion-exclusion. Comb. 10(4): 349-365 (1990) - [j26]Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg:
Improved Routing Strategies with Succinct Tables. J. Algorithms 11(3): 307-341 (1990) - [c17]Nathan Linial, Noam Nisan:
Approximate Inclusion-Exclusion. STOC 1990: 260-270
1980 – 1989
- 1989
- [j25]Michael Ben-Or, Nathan Linial:
Collective Coin Flipping. Adv. Comput. Res. 5: 91-115 (1989) - [j24]David Lichtenstein, Nathan Linial, Michael E. Saks:
Some extremal problems arising form discrete control processes. Comb. 9(3): 269-287 (1989) - [j23]Nathan Linial, Michael Tarsi:
Interpolation Between Bases and the Shuffle Exchange Network. Eur. J. Comb. 10(1): 29-39 (1989) - [j22]Noga Alon, Nathan Linial:
Cycles of length 0 modulo k in directed graphs. J. Comb. Theory B 47(1): 114-119 (1989) - [j21]Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman:
Bounds on Universal Sequences. SIAM J. Comput. 18(2): 268-277 (1989) - [c16]Nathan Linial, Umesh V. Vazirani:
Graph Products and Chromatic Numbers. FOCS 1989: 124-128 - [c15]Nathan Linial, Yishay Mansour, Noam Nisan:
Constant Depth Circuits, Fourier Transform, and Learnability. FOCS 1989: 574-579 - [c14]Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
On the Complexity of Radio Communication (Extended Abstract). STOC 1989: 274-285 - [c13]Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg:
Compact Distributed Data Structures for Adaptive Routing (Extended Abstract). STOC 1989: 479-489 - 1988
- [j20]Ron Aharoni, Paul Erdös, Nathan Linial:
Optima of dual integer linear programs. Comb. 8(1): 13-20 (1988) - [j19]Nathan Linial, László Lovász, Avi Wigderson:
Rubber bands, convex embeddings and graph connectivity. Comb. 8(1): 91-102 (1988) - [j18]Nathan Linial, Roy Meshulam, Michael Tarsi:
Matroidal bijections between graphs. J. Comb. Theory B 45(1): 31-44 (1988) - [j17]Ron Holzman, Ehud Lehrer, Nathan Linial:
Some Bounds for the Banzhaf Index and Other Semivalues. Math. Oper. Res. 13(2): 358-363 (1988) - [c12]Nathan Linial, Yishay Mansour, Ronald L. Rivest:
Results on Learnability and the Vapnick-Chervonenkis Dimension. COLT 1988: 56-68 - [c11]Jeff Kahn, Gil Kalai, Nathan Linial:
The Influence of Variables on Boolean Functions (Extended Abstract). FOCS 1988: 68-80 - [c10]Nathan Linial, Yishay Mansour, Ronald L. Rivest:
Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract). FOCS 1988: 120-129 - 1987
- [j16]Paul Erdös, Nathan Linial, Shlomo Moran:
Extremal problems on permutations under cyclic equivalence. Discret. Math. 64(1): 1-11 (1987) - [c9]Nathan Linial:
Distributive Graph Algorithms-Global Solutions from Local Data. FOCS 1987: 331-335 - [c8]David Lichtenstein, Nathan Linial, Michael E. Saks:
Imperfect Random Sources and Discrete Controlled Processes. STOC 1987: 169-177 - [c7]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal Online Algorithm for Metrical Task Systems. STOC 1987: 373-382 - 1986
- [j15]Nathan Linial:
Legal coloring of graphs. Comb. 6(1): 49-54 (1986) - [j14]Nathan Linial:
Graph coloring and monotone functions on posets. Discret. Math. 58(1): 97-98 (1986) - [j13]Ron Aharoni, Nathan Linial:
Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory A 43(2): 196-204 (1986) - [c6]Nathan Linial, László Lovász, Avi Wigderson:
A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications. FOCS 1986: 39-48 - 1985
- [j12]Nathan Linial, Michael E. Saks:
Searching Ordered Structures. J. Algorithms 6(1): 86-103 (1985) - [j11]Nathan Linial, Michael E. Saks:
Every Poset Has a Central Element. J. Comb. Theory A 40(2): 195-210 (1985) - [j10]Nathan Linial, Michael Tarsi:
Deciding Hypergraph 2-Colourability by H-Resolution. Theor. Comput. Sci. 38: 343-347 (1985) - [c5]Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson:
Multi-Layer Grid Embeddings. FOCS 1985: 186-196 - [c4]Michael Ben-Or, Nathan Linial:
Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values. FOCS 1985: 408-416 - [c3]Ron Aharoni, Paul Erdös, Nathan Linial:
Dual Integer Linear Programs and the Relationship between their Optima. STOC 1985: 476-483 - 1984
- [j9]Nathan Linial:
Graph decompositions without isolates. J. Comb. Theory B 36(1): 16-25 (1984) - [j8]Nathan Linial:
The Information-Theoretic Bound is Good for Merging. SIAM J. Comput. 13(4): 795-801 (1984) - 1983
- [j7]Nathan Linial, Michael E. Saks, Vera T. Sós:
Largest digraphs contained in all n-tournaments. Comb. 3(1): 101-104 (1983) - [c2]Nathan Linial:
Legal Coloring of Graphs. FOCS 1983: 470-472 - [c1]Nathan Linial, Michael E. Saks:
Information Bounds Are Good for Search Problems on Ordered Data Structures. FOCS 1983: 473-475 - 1982
- [j6]Nathan Linial:
A New Derivation of the Counting Formula for Young Tableaux. J. Comb. Theory A 33(3): 340-342 (1982) - [j5]Nathan Linial, Michael Tarsi:
The Counterfeit Coin Problem Revisited. SIAM J. Comput. 11(3): 409-415 (1982) - 1981
- [j4]Nathan Linial:
On Petersen's graph theorem. Discret. Math. 33(1): 53-56 (1981) - [j3]Nathan Linial:
Extending the Greene-Kleitman Theorem to Directed Graphs. J. Comb. Theory A 30(3): 331-334 (1981)
1970 – 1979
- 1978
- [b1]Nathan Linial:
בעיות פירוק וכיסוי בתורת הגרפים (Decomposition and covering problems in graph theory.). Hebrew University of Jerusalem, Israel, 1978 - [j2]Nathan Linial:
Covering digraphs by paths. Discret. Math. 23(3): 257-272 (1978) - 1976
- [j1]Nathan Linial:
A lower bound for the circumference of a graph. Discret. Math. 15(3): 297-300 (1976)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-03-04 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
