Nathan Linial

Orcid: 0000-0002-0918-3136

Affiliations:
  • Hebrew University of Jerusalem, Israel


According to our database1, Nathan Linial authored at least 193 papers between 1976 and 2024.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
On the connectivity and diameter of geodetic graphs.
Eur. J. Comb., February, 2024

The Rank-Ramsey Problem and the Log-Rank Conjecture.
CoRR, 2024

2023
New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes.
IEEE Trans. Inf. Theory, May, 2023

In Search of Hyperpaths.
Discret. Comput. Geom., March, 2023

Irreducible nonmetrizable path systems in graphs.
J. Graph Theory, 2023

An Elementary Proof of the First LP Bound on the Rate of Binary Codes.
CoRR, 2023

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

Linear Programming Hierarchies in Coding Theory: Dual Solutions.
CoRR, 2022

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

Bounds on Unique-Neighbor Codes.
CoRR, 2022

On the Local Structure of Oriented Graphs - a Case Study in Flag Algebras.
Electron. J. Comb., 2022

2021
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

2020
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

Hyperpaths.
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

2019
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

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

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

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

2016
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

2015
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

2014
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

2013
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

2012
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 A, 2012

Strong convergence in posets.
J. Comb. Theory A, 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

2011
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

2010
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

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

Are stable instances easy?
Electron. Colloquium Comput. Complex., 2009

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

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

2007
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

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

On the expansion rate of Margulis expanders.
J. Comb. Theory 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

2005
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 A, 2005

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

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

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

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

2004
Colorings of the d-regular infinite tree.
J. Comb. Theory 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

2003
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

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

A Continuous Analogue of the Girth Problem.
J. Comb. Theory 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

2001
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

2000
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 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

1999
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

1998
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

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

1996
Witness Sets for Families of Binary Vectors.
J. Comb. Theory 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

1995
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

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

Spectral Properties of Threshold Functions.
Comb., 1994

1993
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

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

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

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

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

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

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

Additive bases of vector spaces over prime fields.
J. Comb. Theory 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

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

Approximate inclusion-exclusion.
Comb., 1990

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

Cycles of length 0 modulo <i>k</i> in directed graphs.
J. Comb. Theory 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

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

Matroidal bijections between graphs.
J. Comb. Theory 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

1987
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

1986
Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas.
J. Comb. Theory 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

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

Every Poset Has a Central Element.
J. Comb. Theory 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

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

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

1983
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

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

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

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

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

1978
בעיות פירוק וכיסוי בתורת הגרפים (Decomposition and covering problems in graph theory.).
PhD thesis, 1978

Covering digraphs by paths.
Discret. Math., 1978

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


  Loading...