Nathan Linial

According to our database1, Nathan Linial authored at least 171 papers between 1976 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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.
Combinatorics, Probability & Computing, 2018

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

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

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

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

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

Invariants of Random Knots and Links.
Discrete & Computational Geometry, 2016

On the densities of cliques and independent sets in graphs.
Combinatorica, 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.
Journal of Graph Theory, 2015

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

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

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

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

On the Vertices of the d-Dimensional Birkhoff Polytope.
Discrete & Computational Geometry, 2014

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

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

Entropy-driven partitioning of the hierarchical protein space.
Bioinformatics, 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.
Discrete & Computational Geometry, 2013

Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes.
Discrete & Computational Geometry, 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 Research, 2012

Tight products and graph expansion.
Journal of 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

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

2011
The Expected Genus of a Random Chord Diagram.
Discrete & Computational Geometry, 2011

Generative probabilistic models for protein-protein interaction networks - the biclique perspective.
Bioinformatics [ISMB/ECCB], 2011

Recovering key biological constituents through sparse representation of gene expression.
Bioinformatics, 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.
Discrete & Computational Geometry, 2010

Are Stable Instances Easy?
Proceedings of the Innovations in Computer Science, 2010

2009
Learning Complexity vs Communication Complexity.
Combinatorics, Probability & Computing, 2009

2008
Graph Colouring with No Large Monochromatic Components.
Combinatorics, Probability & Computing, 2008

Learning Complexity vs. Communication Complexity.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

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

Graph coloring with no large monochromatic components.
Electronic Notes in Discrete Mathematics, 2007

Complexity measures of sign matrices.
Combinatorica, 2007

Lower bounds in communication complexity based on factorization norms.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Eigenvectors of Random Graphs: Nodal Domains.
Proceedings of the Approximation, 2007

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

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

How Neighborly Can a Centrally Symmetric Polytope Be?
Discrete & Computational Geometry, 2006

Random Lifts of Graphs: Edge Expansion.
Combinatorics, Probability & Computing, 2006

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

Homological Connectivity Of Random 2-Complexes.
Combinatorica, 2006

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

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

2005
ProtoNet 4.0: A hierarchical classification of one million protein sequences.
Nucleic Acids Research, 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 chi-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.
Discrete & Computational Geometry, 2005

Random Lifts Of Graphs: Perfekt Matchings.
Combinatorica, 2005

Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis.
Proceedings of the Research in Computational Molecular Biology, 2005

2004
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.
Discrete & Computational Geometry, 2004

Ramanujan Signing of Regular Graphs.
Combinatorics, Probability & Computing, 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 Research, 2003

The Euclidean Distortion of Complete Binary Trees.
Discrete & Computational Geometry, 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, Ser. B, 2002

An Extremal Problem on Degree Sequences of Graphs.
Graphs and Combinatorics, 2002

The Moore Bound for Irregular Graphs.
Graphs and Combinatorics, 2002

Linear Codes and Character Sums.
Combinatorica, 2002

Random Graph Coverings I: General Theory and Graph Connectivity.
Combinatorica, 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, Barcelona, 2002

The one-round Voronoi game.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

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

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

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

Competitive Optimal On-Line Leasing.
Algorithmica, 1999

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

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 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

1996
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).
Discrete & Computational Geometry, 1996

Inclusion-Exclusion: Exact and Approximate.
Combinatorica, 1996

Biased Random Walks.
Combinatorica, 1996

Non-Expansive Hashing.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

The Linear-Array Conjecture in Communication Complexity is False.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

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

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

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

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

Spectral Properties of Threshold Functions.
Combinatorica, 1994

Neighborhood Preserving Hashing and Approximate Queries.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

The geometry of graphs and some of its algorithmic applications
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

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

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

Combinatorial characterization of read-once formulae.
Discrete Mathematics, 1993

On Convex Body Chasing.
Discrete & Computational Geometry, 1993

Local-Global Phenomena in Graphs.
Combinatorics, Probability & Computing, 1993

Low diameter graph decompositions.
Combinatorica, 1993

The influence of large coalitions.
Combinatorica, 1993

Efficient construction of a small hitting set for combinatorial rectangles in high dimension.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 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

On the Hardness of Approximating the Chromatic Number.
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, 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

Biased Random Walks
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 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, Ser. A, 1991

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

Balancing extensions via Brunn-Minkowski.
Combinatorica, 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.
Combinatorica, 1990

Approximate Inclusion-Exclusion
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

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

Cycles of length 0 modulo k 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.
Combinatorica, 1989

Collective Coin Flipping.
Advances in Computing Research, 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

Constant Depth Circuits, Fourier Transform, and Learnability
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, Ser. B, 1988

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

Optima of dual integer linear programs.
Combinatorica, 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.
Discrete Mathematics, 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, Ser. A, 1986

Graph coloring and monotone functions on posets.
Discrete Mathematics, 1986

Legal coloring of graphs.
Combinatorica, 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, 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

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

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

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

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

Legal Coloring of Graphs
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, Ser. A, 1982

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

On Petersen's graph theorem.
Discrete Mathematics, 1981

1978
Covering digraphs by paths.
Discrete Mathematics, 1978

1976
A lower bound for the circumference of a graph.
Discrete Mathematics, 1976


  Loading...