Nathan Linial

Redirect to:

• Nathan Linial

MaRDI QIDQ178480zbMATH OpenDBLPWikidataFDO

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
The structure of metrizable graphs Discrete & Computational Geometry	2026-01-05	Paper
An approach to the girth problem in cubic graphs Journal of Graph Theory	2025-11-24	Paper
Bounds on unique-neighbor codes Combinatorial Theory	2025-11-14	Paper
On the Löwner-John ellipsoids of the metric polytope Discrete & Computational Geometry	2025-09-24	Paper
Expander graphs -- both local and global	2025-08-12	Paper
How balanced can permutations be? Combinatorica	2025-04-08	Paper
New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes IEEE Transactions on Information Theory	2024-03-19	Paper
On the connectivity and diameter of geodetic graphs European Journal of Combinatorics	2024-02-05	Paper
The Structure of Metrizable Graphs	2023-11-15	Paper
A randomized construction of high girth regular graphs Random Structures & Algorithms	2023-10-11	Paper
Irreducible nonmetrizable path systems in graphs Journal of Graph Theory	2023-10-05	Paper
An improved protocol for the exactly-N problem*	2023-07-12	Paper
How Balanced Can Permutations Be?	2023-06-29	Paper
On the L\"owner-John Ellipsoids of the Metric Polytope	2023-04-19	Paper
In search of hyperpaths Discrete & Computational Geometry	2023-03-15	Paper
On the local structure of oriented graphs -- a case study in flag algebras The Electronic Journal of Combinatorics	2022-09-06	Paper
On the communication complexity of high-dimensional permutations (available as arXiv preprint)	2022-07-18	Paper
An approach to the girth problem in cubic graphs	2022-06-29	Paper
On the densities of cliques and independent sets in graphs Combinatorica	2022-06-29	Paper
Geodesic geometry on graphs Discrete & Computational Geometry	2022-06-03	Paper
Bounds on Unique-Neighbor Codes	2022-03-19	Paper
Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols discrete Analysis	2022-02-10	Paper
Efficient, local and symmetric Markov chains that generate one-factorizations Acta Mathematica Hungarica	2020-12-18	Paper
Hyperpaths (available as arXiv preprint)	2020-11-19	Paper
On the weight distribution of random binary linear codes Random Structures & Algorithms	2020-06-19	Paper
Asymptotically almost every \(2r\)-regular graph has an internal partition Graphs and Combinatorics	2020-03-03	Paper
Enumeration and randomized constructions of hypertrees Random Structures & Algorithms	2019-11-28	Paper
A King in every two consecutive tournaments	2019-10-21	Paper
Universal knot diagrams Journal of Knot Theory and Its Ramifications	2019-07-04	Paper
Extremal hypercuts and shadows of simplicial complexes Israel Journal of Mathematics	2019-02-07	Paper
The distribution of knots in the Petaluma model Algebraic & Geometric Topology	2018-12-06	Paper
The one-round Voronoi game Proceedings of the eighteenth annual symposium on Computational geometry	2018-11-23	Paper
Random simplicial complexes: around the phase transition A Journey Through Discrete Mathematics	2018-02-26	Paper
Monotone subsequences in high-dimensional permutations Combinatorics, Probability and Computing	2018-01-19	Paper
On the Rigidity of Sparse Random Graphs Journal of Graph Theory	2017-07-05	Paper
Efficient Generation of One-Factorizations through Hill Climbing	2017-07-03	Paper
On The Communication Complexity of High-Dimensional Permutations (available as arXiv preprint)	2017-06-07	Paper
On the practically interesting instances of MAXCUT (available as arXiv preprint)	2017-01-30	Paper
On the number of 4-cycles in a tournament Journal of Graph Theory	2016-11-16	Paper
On the phase transition in random simplicial complexes Annals of Mathematics. Second Series	2016-11-04	Paper
Internal partitions of regular graphs Journal of Graph Theory	2016-10-13	Paper
Discrepancy of high-dimensional permutations Discrete Analysis	2016-10-10	Paper
No justified complaints: on fair sharing of multiple resources Proceedings of the 3rd Innovations in Theoretical Computer Science Conference	2016-10-07	Paper
Invariants of random knots and links Discrete & Computational Geometry	2016-09-14	Paper
The threshold for \(d\)-collapsibility in random complexes Random Structures & Algorithms	2016-03-22	Paper
On the local profiles of trees Journal of Graph Theory	2016-02-01	Paper
A note on the inducibility of 4-vertex graphs Graphs and Combinatorics	2015-09-24	Paper
From average case complexity to improper learning complexity Proceedings of the forty-sixth annual ACM symposium on Theory of computing	2015-06-26	Paper
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 - STOC '93	2015-05-07	Paper
Fast perfection-information leader-election protocol with linear immunity Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93	2015-05-07	Paper
Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal Journal of Graph Theory	2015-03-24	Paper
Triply existentially complete triangle-free graphs Journal of Graph Theory	2015-03-24	Paper
When does the top homology of a random simplicial complex vanish? Random Structures & Algorithms	2015-02-20	Paper
An upper bound on the number of high-dimensional permutations Combinatorica	2015-01-08	Paper
Musical Chairs SIAM Journal on Discrete Mathematics	2014-12-22	Paper
On regular hypergraphs of high girth The Electronic Journal of Combinatorics	2014-09-04	Paper
On regular hypergraphs of high girth The Electronic Journal of Combinatorics	2014-09-04	Paper
On the 3-local profiles of graphs Journal of Graph Theory	2014-08-07	Paper
Extremal problems on shadows and hypercuts in simplicial complexes	2014-08-04	Paper
Chernoff's Inequality - A very elementary proof	2014-03-30	Paper
On the vertices of the \(d\)-dimensional Birkhoff polytope Discrete & Computational Geometry	2014-03-25	Paper
On high-dimensional acyclic tournaments Discrete & Computational Geometry	2014-01-24	Paper
An upper bound on the number of Steiner triple systems Random Structures & Algorithms	2013-12-23	Paper
Collapsibility and vanishing of top homology in random simplicial complexes Discrete & Computational Geometry	2013-03-20	Paper
Are stable instances easy? Combinatorics, Probability and Computing	2012-09-12	Paper
Tight products and graph expansion Journal of Graph Theory	2012-06-13	Paper
Strong convergence in posets Journal of Combinatorial Theory. Series A	2012-06-04	Paper
On the Lipschitz constant of the RSK correspondence Journal of Combinatorial Theory. Series A	2011-11-11	Paper
Oblivious Collaboration Lecture Notes in Computer Science	2011-10-28	Paper
Eigenvectors of random graphs: nodal domains Random Structures & Algorithms	2011-08-09	Paper
The expected genus of a random chord diagram Discrete & Computational Geometry	2011-03-10	Paper
Word maps and spectra of random graph lifts Random Structures & Algorithms	2010-11-24	Paper
On metric Ramsey-type phenomena Proceedings of the thirty-fifth annual ACM symposium on Theory of computing	2010-08-16	Paper
Girth and euclidean distortion Proceedings of the thiry-fourth annual ACM symposium on Theory of computing	2010-08-05	Paper
Learning complexity vs communication complexity Combinatorics, Probability and Computing	2010-04-23	Paper
Lower bounds in communication complexity based on factorization norms Random Structures & Algorithms	2009-06-16	Paper
Eigenvectors of Random Graphs: Nodal Domains Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2009-02-17	Paper
Lower bounds in communication complexity based on factorization norms Proceedings of the thirty-ninth annual ACM symposium on Theory of computing	2009-01-05	Paper
Complexity measures of sign matrices Combinatorica	2008-10-21	Paper
Graph colouring with no large monochronomatic components Combinatorics, Probability and Computing	2008-09-29	Paper
Expander graphs and their applications Bulletin of the American Mathematical Society	2008-07-21	Paper
Graph coloring with no large monochromatic components Electronic Notes in Discrete Mathematics	2008-06-05	Paper
Limitations to Fréchet's metric embedding method Israel Journal of Mathematics	2007-10-09	Paper
Lifts, discrepancy and nearly optimal spectral gap Combinatorica	2007-05-08	Paper
Minors in lifts of graphs Random Structures & Algorithms	2007-02-07	Paper
Homological connectivity of random 2-complexes Combinatorica	2007-01-08	Paper
How neighborly can a centrally symmetric polytope be? Discrete & Computational Geometry	2006-10-04	Paper
On metric Ramsey-type phenomena Annals of Mathematics. Second Series	2006-07-26	Paper
Random Lifts of Graphs: Edge Expansion Combinatorics, Probability and Computing	2006-07-06	Paper
Random lifts of graphs: perfect matchings Combinatorica	2006-06-27	Paper
On the expansion rate of Margulis expanders. Journal of Combinatorial Theory. Series B	2006-05-18	Paper
The non-crossing graph The Electronic Journal of Combinatorics	2006-01-31	Paper
The non-crossing graph The Electronic Journal of Combinatorics	2006-01-31	Paper
Research in Computational Molecular Biology Lecture Notes in Computer Science	2005-11-23	Paper
A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex Journal of Combinatorial Theory. Series B	2005-11-22	Paper
Monotone maps, sphericity and bounded second eigenvalue Journal of Combinatorial Theory. Series B	2005-11-22	Paper
ON METRIC RAMSEY-TYPE DICHOTOMIES Journal of the London Mathematical Society	2005-05-23	Paper
Essential covers of the cube by hyperplanes Journal of Combinatorial Theory. Series A	2005-04-06	Paper
Some low distortion metric Ramsey problems Discrete & Computational Geometry	2005-02-23	Paper
Ramanujan Signing of Regular Graphs Combinatorics, Probability and Computing	2005-02-18	Paper
Metric embeddings -- beyond one-dimensional distortion Discrete & Computational Geometry	2004-12-16	Paper
Colorings of the \(d\)-regular infinite tree Journal of Combinatorial Theory. Series B	2004-08-06	Paper
The one-round Voronoi game Discrete & Computational Geometry	2004-03-11	Paper
Low dimensional embeddings of ultrametrics. European Journal of Combinatorics	2004-02-14	Paper
scientific article; zbMATH DE number 1775401 (Why is no real title available?)	2004-02-08	Paper
Linear codes and character sums Combinatorica	2003-10-14	Paper
An extremal problem on degree sequences of graphs Graphs and Combinatorics	2003-03-25	Paper
The Euclidean distortion of complete binary trees Discrete & Computational Geometry	2003-03-17	Paper
Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders Journal of Combinatorial Theory. Series B	2002-12-10	Paper
A continuous analogue of the girth problem Journal of Combinatorial Theory. Series B	2002-12-10	Paper
scientific article; zbMATH DE number 1789916 (Why is no real title available?) (available as arXiv preprint)	2002-11-10	Paper
Random graph coverings. I: General theory and graph connectivity Combinatorica	2002-10-20	Paper
Random lifts of graphs: Independence and chromatic number Random Structures & Algorithms	2002-09-20	Paper
scientific article; zbMATH DE number 1775454 (Why is no real title available?)	2002-09-17	Paper
Girth and Euclidean distortion Geometric and Functional Analysis. GAFA	2002-07-29	Paper
Random lifts of graphs	2002-06-03	Paper
The Moore bound for irregular graphs Graphs and Combinatorics	2002-05-14	Paper
Neighborhood preserving hashing and approximate queries SIAM Journal on Discrete Mathematics	2002-04-23	Paper
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents Combinatorica	2001-06-13	Paper
On the hardness of approximating the chromatic number Combinatorica	2001-06-12	Paper
Low distortion Euclidean embeddings of trees Israel Journal of Mathematics	2000-06-05	Paper
Competitive optimal on-line leasing Algorithmica	2000-01-04	Paper
The linear-array conjecture in communication complexity is false Combinatorica	1999-12-08	Paper
Non-expansive hashing Combinatorica	1999-10-31	Paper
A note on the influence of an \(\epsilon\)-biased random source Journal of Computer and System Sciences	1999-09-22	Paper
scientific article; zbMATH DE number 1256713 (Why is no real title available?)	1999-05-18	Paper
scientific article; zbMATH DE number 1256770 (Why is no real title available?)	1999-03-01	Paper
scientific article; zbMATH DE number 1226101 (Why is no real title available?)	1999-01-03	Paper
scientific article; zbMATH DE number 1146220 (Why is no real title available?)	1998-10-15	Paper
Fault-tolerant Computation in the Full Information Model SIAM Journal on Computing	1998-05-10	Paper
Efficient construction of a small hitting set for combinatorial rectangles in high dimension Combinatorica	1998-03-26	Paper
Inclusion-exclusion: exact and approximate Combinatorica	1998-01-11	Paper
scientific article; zbMATH DE number 1047739 (Why is no real title available?)	1997-08-11	Paper
scientific article; zbMATH DE number 1003256 (Why is no real title available?)	1997-04-23	Paper
Biased random walks Combinatorica	1996-09-16	Paper
Central points for sets in \(\mathbb{R}^ n\) (or: the chocolate ice-cream problem) Discrete & Computational Geometry	1996-07-29	Paper
Witness sets for families of binary vectors Journal of Combinatorial Theory. Series A	1996-02-26	Paper
On the distance distribution of codes IEEE Transactions on Information Theory	1996-02-12	Paper
Fast perfect-information leader-election protocols with linear immunity Combinatorica	1995-10-17	Paper
The geometry of graphs and some of its algorithmic applications Combinatorica	1995-07-24	Paper
Spectral properties of threshold functions Combinatorica	1995-04-18	Paper
An optimal on-line algorithm for metrical task system Journal of the ACM	1994-08-21	Paper
Local and global clique numbers Journal of Combinatorial Theory. Series B	1994-07-04	Paper
Low diameter graph decompositions Combinatorica	1994-06-22	Paper
Local-Global Phenomena in Graphs Combinatorics, Probability and Computing	1994-04-28	Paper
Constant depth circuits, Fourier transform, and learnability Journal of the ACM	1993-12-09	Paper
Combinatorial characterization of read-once formulae Discrete Mathematics	1993-10-24	Paper
scientific article; zbMATH DE number 432834 (Why is no real title available?)	1993-10-20	Paper
The influence of variables in product spaces Israel Journal of Mathematics	1993-10-04	Paper
The influence of large coalitions Combinatorica	1993-09-15	Paper
On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels IEEE Transactions on Information Theory	1993-05-16	Paper
On convex body chasing Discrete & Computational Geometry	1993-05-16	Paper
Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties Journal of Combinatorial Theory. Series B	1993-03-10	Paper
scientific article; zbMATH DE number 109188 (Why is no real title available?)	1993-03-09	Paper
The equivalence of two problems on the cube Journal of Combinatorial Theory. Series A	1992-10-05	Paper
Single round simulation on radio networks Journal of Algorithms	1992-06-28	Paper
Locality in Distributed Graph Algorithms SIAM Journal on Computing	1992-06-28	Paper
Balancing extensions via Brunn-Minkowski Combinatorica	1992-06-27	Paper
Additive bases of vector spaces over prime fields Journal of Combinatorial Theory. Series A	1992-06-25	Paper
A lower bound for radio broadcast Journal of Computer and System Sciences	1992-06-25	Paper
Approximate inclusion-exclusion Combinatorica	1992-06-25	Paper
Results on learnability and the Vapnik-Chervonenkis dimension Information and Computation	1991-01-01	Paper
A lower bound on the area of permutation layouts Algorithmica	1991-01-01	Paper
Improved routing strategies with succinct tables Journal of Algorithms	1990-01-01	Paper
scientific article; zbMATH DE number 4119974 (Why is no real title available?)	1989-01-01	Paper
Cycles of length 0 modulo k in directed graphs Journal of Combinatorial Theory. Series B	1989-01-01	Paper
Interpolation between bases and the shuffle exchange network European Journal of Combinatorics	1989-01-01	Paper
On the cover time of random walks on graphs Journal of Theoretical Probability	1989-01-01	Paper
Bounds on Universal Sequences SIAM Journal on Computing	1989-01-01	Paper
Some extremal problems arising from discrete control processes Combinatorica	1989-01-01	Paper
scientific article; zbMATH DE number 4106654 (Why is no real title available?)	1988-01-01	Paper
Matroidal bijections between graphs Journal of Combinatorial Theory. Series B	1988-01-01	Paper
Rubber bands, convex embeddings and graph connectivity Combinatorica	1988-01-01	Paper
Optima of dual integer linear programs Combinatorica	1988-01-01	Paper
Some Bounds for the Banzhaf Index and Other Semivalues Mathematics of Operations Research	1988-01-01	Paper
Extremal problems on permutations under cyclic equivalence Discrete Mathematics	1987-01-01	Paper
Hard Enumeration Problems in Geometry and Combinatorics SIAM Journal on Algebraic Discrete Methods	1986-01-01	Paper
Legal coloring of graphs Combinatorica	1986-01-01	Paper
Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas Journal of Combinatorial Theory. Series A	1986-01-01	Paper
Graph coloring and monotone functions on posets Discrete Mathematics	1986-01-01	Paper
Searching ordered structures Journal of Algorithms	1985-01-01	Paper
Every poset has a central element Journal of Combinatorial Theory. Series A	1985-01-01	Paper
Deciding hypergraph 2-colourability by H-resolution Theoretical Computer Science	1985-01-01	Paper
Largest induced suborders satisfying the chain condition Order	1985-01-01	Paper
Graph decompositions without isolates Journal of Combinatorial Theory. Series B	1984-01-01	Paper
The Information-Theoretic Bound is Good for Merging SIAM Journal on Computing	1984-01-01	Paper
scientific article; zbMATH DE number 3851127 (Why is no real title available?)	1983-01-01	Paper
Largest digraphs contained in all n-tournaments Combinatorica	1983-01-01	Paper
The Counterfeit Coin Problem Revisited SIAM Journal on Computing	1982-01-01	Paper
A new derivation of the counting formula for Young tableaux Journal of Combinatorial Theory. Series A	1982-01-01	Paper
Incidence Matrices of Subsets—A Rank Formula SIAM Journal on Algebraic Discrete Methods	1981-01-01	Paper
Extending the Greene-Kleitman theorem to directed graphs Journal of Combinatorial Theory. Series A	1981-01-01	Paper
On Petersen's graph theorem Discrete Mathematics	1981-01-01	Paper
Covering digraphs by paths Discrete Mathematics	1978-01-01	Paper
A lower bound for the circumference of a graph Discrete Mathematics	1976-01-01	Paper

Research outcomes over time

This page was built for person: Nathan Linial