Nathan Linial

  • Hebrew University of Jerusalem, Israel

According to our database1, Nathan Linial authored at least 184 papers between 1976 and 2022.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:



Geodesic Geometry on Graphs.
Discret. Comput. Geom., 2022

New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes.
CoRR, 2022

Bounds on Unique-Neighbor Codes.
CoRR, 2022

A randomized construction of high girth regular graphs.
Random Struct. Algorithms, 2021

An Improved Protocol for the Exactly-N Problem.
Proceedings of the 36th Computational Complexity Conference, 2021

On the weight distribution of random binary linear codes.
Random Struct. Algorithms, 2020

Asymptotically Almost Every 2r-Regular Graph Has an Internal Partition.
Graphs Comb., 2020

CoRR, 2020

Expander Graphs - Both Local and Global.
Comb., 2020

PWAS: Proteome-Wide Association Study.
Proceedings of the Research in Computational Molecular Biology, 2020

Functional Evolutionary Modeling Exposes Overlooked Protein-Coding Genes Involved in Cancer.
Proceedings of the Bioinformatics Research and Applications - 16th International Symposium, 2020

Enumeration and randomized constructions of hypertrees.
Random Struct. Algorithms, 2019

A cell-based probabilistic approach unveils the concerted action of miRNAs.
PLoS Comput. Biol., 2019

A King in every two consecutive tournaments.
CoRR, 2019

On the Communication Complexity of High-Dimensional Permutations.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Monotone Subsequences in High-Dimensional Permutations.
Comb. Probab. Comput., 2018

On the Rigidity of Sparse Random Graphs.
J. Graph Theory, 2017

On The Communication Complexity of High-Dimensional Permutations.
CoRR, 2017

The threshold for d-collapsibility in random complexes.
Random Struct. Algorithms, 2016

On the Number of 4-Cycles in a Tournament.
J. Graph Theory, 2016

On the Local Profiles of Trees.
J. Graph Theory, 2016

Internal Partitions of Regular Graphs.
J. Graph Theory, 2016

Invariants of Random Knots and Links.
Discret. Comput. Geom., 2016

On the densities of cliques and independent sets in graphs.
Comb., 2016

When does the top homology of a random simplicial complex vanish?
Random Struct. Algorithms, 2015

Graphs with Few 3-Cliques and 3-Anticliques are 3-Universal.
J. Graph Theory, 2015

Triply Existentially Complete Triangle-Free Graphs.
J. Graph Theory, 2015

A Note on the Inducibility of 4-Vertex Graphs.
Graphs Comb., 2015

Musical Chairs.
SIAM J. Discret. Math., 2014

On the 3-Local Profiles of Graphs.
J. Graph Theory, 2014

On the Vertices of the d-Dimensional Birkhoff Polytope.
Discret. Comput. Geom., 2014

Market Share Indicates Quality.
CoRR, 2014

On Regular Hypergraphs of High Girth.
Electron. J. Comb., 2014

An upper bound on the number of high-dimensional permutations.
Comb., 2014

Entropy-driven partitioning of the hierarchical protein space.
Bioinform., 2014

From average case complexity to improper learning complexity.
Proceedings of the Symposium on Theory of Computing, 2014

The Complexity of Learning Halfspaces using Generalized Linear Methods.
Proceedings of The 27th Conference on Learning Theory, 2014

An upper bound on the number of Steiner triple systems.
Random Struct. Algorithms, 2013

On High-Dimensional Acyclic Tournaments.
Discret. Comput. Geom., 2013

Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes.
Discret. Comput. Geom., 2013

On the practically interesting instances of MAXCUT.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

More data speeds up training time in learning halfspaces over sparse vectors.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

ProtoNet 6.0: organizing 10 million protein sequences in a compact hierarchical family tree.
Nucleic Acids Res., 2012

Tight products and graph expansion.
J. Graph Theory, 2012

On the Lipschitz constant of the RSK correspondence.
J. Comb. Theory, Ser. A, 2012

Strong convergence in posets.
J. Comb. Theory, Ser. A, 2012

Are Stable Instances Easy?
Comb. Probab. Comput., 2012

The error rate of learning halfspaces using Kernel-SVMs
CoRR, 2012

Clustering is difficult only when it does not matter
CoRR, 2012

No justified complaints: on fair sharing of multiple resources.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Eigenvectors of random graphs: Nodal Domains.
Random Struct. Algorithms, 2011

The Expected Genus of a Random Chord Diagram.
Discret. Comput. Geom., 2011

Generative probabilistic models for protein-protein interaction networks - the biclique perspective.
Bioinform., 2011

Recovering key biological constituents through sparse representation of gene expression.
Bioinform., 2011

Oblivious Collaboration.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

The dynamics of reputation systems.
Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), 2011

Geometric Interpretation of Gene Expression by Sparse Reconstruction of Transcript Profiles.
Proceedings of the Research in Computational Molecular Biology, 2011

Word maps and spectra of random graph lifts.
Random Struct. Algorithms, 2010

Sum Complexes - a New Family of Hypertrees.
Discret. Comput. Geom., 2010

Tight products and Expansion
CoRR, 2010

Lower bounds in communication complexity based on factorization norms.
Random Struct. Algorithms, 2009

Learning Complexity vs Communication Complexity.
Comb. Probab. Comput., 2009

Graph Colouring with No Large Monochromatic Components.
Comb. Probab. Comput., 2008

EVEREST: a collection of evolutionary conserved protein domains.
Nucleic Acids Res., 2007

Graph coloring with no large monochromatic components.
Electron. Notes Discret. Math., 2007

Complexity measures of sign matrices.
Comb., 2007

Minors in lifts of graphs.
Random Struct. Algorithms, 2006

On the expansion rate of Margulis expanders.
J. Comb. Theory, Ser. B, 2006

Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis.
J. Comput. Biol., 2006

How Neighborly Can a Centrally Symmetric Polytope Be?
Discret. Comput. Geom., 2006

Random Lifts of Graphs: Edge Expansion.
Comb. Probab. Comput., 2006

The Non-Crossing Graph.
Electron. J. Comb., 2006

Homological Connectivity Of Random 2-Complexes.
Comb., 2006

Lifts, Discrepancy and Nearly Optimal Spectral Gap*.
Comb., 2006

EVEREST: automatic identification and classification of protein domains in all protein sequences.
BMC Bioinform., 2006

ProtoNet 4.0: A hierarchical classification of one million protein sequences.
Nucleic Acids Res., 2005

Essential covers of the cube by hyperplanes.
J. Comb. Theory, Ser. A, 2005

A counterexample to a conjecture of Björner and Lovász on the <i>chi</i>-coloring complex.
J. Comb. Theory, Ser. B, 2005

Monotone maps, sphericity and bounded second eigenvalue.
J. Comb. Theory, Ser. B, 2005

Some Low Distortion Metric Ramsey Problems.
Discret. Comput. Geom., 2005

Random Lifts Of Graphs: Perfekt Matchings.
Comb., 2005

Colorings of the d-regular infinite tree.
J. Comb. Theory, Ser. B, 2004

Low dimensional embeddings of ultrametrics.
Eur. J. Comb., 2004

Metric Embeddings--Beyond One-Dimensional Distortion.
Discret. Comput. Geom., 2004

The One-Round Voronoi Game.
Discret. Comput. Geom., 2004

Ramanujan Signing of Regular Graphs.
Comb. Probab. Comput., 2004

Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

ProtoNet: hierarchical classification of the protein space.
Nucleic Acids Res., 2003

The Euclidean Distortion of Complete Binary Trees.
Discret. Comput. Geom., 2003

On metric ramsey-type phenomena.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Random lifts of graphs: Independence and chromatic number.
Random Struct. Algorithms, 2002

A Continuous Analogue of the Girth Problem.
J. Comb. Theory, Ser. B, 2002

An Extremal Problem on Degree Sequences of Graphs.
Graphs Comb., 2002

The Moore Bound for Irregular Graphs.
Graphs Comb., 2002

Linear Codes and Character Sums.
Comb., 2002

Random Graph Coverings I: General Theory and Graph Connectivity.
Comb., 2002

Girth and euclidean distortion.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The metric space of proteins-comparative study of clustering algorithms.
Proceedings of the Tenth International Conference on Intelligent Systems for Molecular Biology, 2002

Finite metric spaces: combinatorics, geometry and algorithms.
Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

Neighborhood Preserving Hashing and Approximate Queries.
SIAM J. Discret. Math., 2001

Random lifts of graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

ProtoMap: automatic classification of protein sequences and hierarchy of protein families.
Nucleic Acids Res., 2000

Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders.
J. Comb. Theory, Ser. B, 2000

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Comb., 2000

On the Hardness of Approximating the Chromatic Number.
Comb., 2000

A Note on the Influence of an epsilon-Biased Random Source.
J. Comput. Syst. Sci., 1999

The Linear-Array Conjecture in Communication Complexity Is False.
Comb., 1999

Competitive Optimal On-Line Leasing.
Algorithmica, 1999

Fault-Tolerant Computation in the Full Information Model.
SIAM J. Comput., 1998

Non-Expansive Hashing.
Comb., 1998

Trees and Euclidean Metrics.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

A Map of the Protein Space: An Automatic Hierarchical Classification of all Protein Sequences.
Proceedings of the 6th International Conference on Intelligent Systems for Molecular Biology (ISMB-98), Montréal, Québec, Canada, June 28, 1998

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.
Comb., 1997

Witness Sets for Families of Binary Vectors.
J. Comb. Theory, Ser. A, 1996

Central Points for Sets in Rn (or: the Chocolate Ice-Cream Problem).
Discret. Comput. Geom., 1996

Inclusion-Exclusion: Exact and Approximate.
Comb., 1996

Biased Random Walks.
Comb., 1996

On the distance distribution of codes.
IEEE Trans. Inf. Theory, 1995

The Geometry of Graphs and Some of its Algorithmic Applications.
Comb., 1995

Fast Perfect-Information Leader-Election Protocols with Linear Immunity.
Comb., 1995

Local and Global Clique Numbers.
J. Comb. Theory, Ser. B, 1994

Spectral Properties of Threshold Functions.
Comb., 1994

On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels.
IEEE Trans. Inf. Theory, 1993

Constant Depth Circuits, Fourier Transform, and Learnability.
J. ACM, 1993

Combinatorial characterization of read-once formulae.
Discret. Math., 1993

On Convex Body Chasing.
Discret. Comput. Geom., 1993

Local-Global Phenomena in Graphs.
Comb. Probab. Comput., 1993

Low diameter graph decompositions.
Comb., 1993

The influence of large coalitions.
Comb., 1993

Fast perfection-information leader-election protocol with linear immunity.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Sphere Packing and Local Majorities in Graphs.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Locality in Distributed Graph Algorithms.
SIAM J. Comput., 1992

Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties.
J. Comb. Theory, Ser. B, 1992

The Equivalence of Two Problems on the Cube.
J. Comb. Theory, Ser. A, 1992

Single Round Simulation on Radio Networks.
J. Algorithms, 1992

An Optimal On-Line Algorithm for Metrical Task System.
J. ACM, 1992

Results on Learnability and the Vapnik-Chervonenkis Dimension
Inf. Comput., January, 1991

Additive bases of vector spaces over prime fields.
J. Comb. Theory, Ser. A, 1991

A Lower Bound for Radio Broadcast.
J. Comput. Syst. Sci., 1991

Balancing extensions via Brunn-Minkowski.
Comb., 1991

A Lower Bound on the Area of Permutation Layouts.
Algorithmica, 1991

Decomposing Graphs into Regions of Small Diameter.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Fault-tolerant Computation in the Full Information Model (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Improved Routing Strategies with Succinct Tables.
J. Algorithms, 1990

Approximate inclusion-exclusion.
Comb., 1990

Bounds on Universal Sequences.
SIAM J. Comput., 1989

Cycles of length 0 modulo <i>k</i> in directed graphs.
J. Comb. Theory, Ser. B, 1989

Interpolation Between Bases and the Shuffle Exchange Network.
Eur. J. Comb., 1989

Some extremal problems arising form discrete control processes.
Comb., 1989

Collective Coin Flipping.
Adv. Comput. Res., 1989

Compact Distributed Data Structures for Adaptive Routing (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On the Complexity of Radio Communication (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Graph Products and Chromatic Numbers
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Some Bounds for the Banzhaf Index and Other Semivalues.
Math. Oper. Res., 1988

Matroidal bijections between graphs.
J. Comb. Theory, Ser. B, 1988

Rubber bands, convex embeddings and graph connectivity.
Comb., 1988

Optima of dual integer linear programs.
Comb., 1988

Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

The Influence of Variables on Boolean Functions (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Results on Learnability and the Vapnick-Chervonenkis Dimension.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

Extremal problems on permutations under cyclic equivalence.
Discret. Math., 1987

Imperfect Random Sources and Discrete Controlled Processes
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

An Optimal Online Algorithm for Metrical Task Systems
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Distributive Graph Algorithms-Global Solutions from Local Data
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas.
J. Comb. Theory, Ser. A, 1986

Graph coloring and monotone functions on posets.
Discret. Math., 1986

Legal coloring of graphs.
Comb., 1986

A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Deciding Hypergraph 2-Colourability by H-Resolution.
Theor. Comput. Sci., 1985

Every Poset Has a Central Element.
J. Comb. Theory, Ser. A, 1985

Searching Ordered Structures.
J. Algorithms, 1985

Dual Integer Linear Programs and the Relationship between their Optima
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Multi-Layer Grid Embeddings
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

The Information-Theoretic Bound is Good for Merging.
SIAM J. Comput., 1984

Graph decompositions without isolates.
J. Comb. Theory, Ser. B, 1984

Largest digraphs contained in all n-tournaments.
Comb., 1983

Information Bounds Are Good for Search Problems on Ordered Data Structures
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

The Counterfeit Coin Problem Revisited.
SIAM J. Comput., 1982

A New Derivation of the Counting Formula for Young Tableaux.
J. Comb. Theory, Ser. A, 1982

Extending the Greene-Kleitman Theorem to Directed Graphs.
J. Comb. Theory, Ser. A, 1981

On Petersen's graph theorem.
Discret. Math., 1981

Covering digraphs by paths.
Discret. Math., 1978

A lower bound for the circumference of a graph.
Discret. Math., 1976