Publications (58)
Oblivious Collaboration
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize this quest…
Graphs with few 3-cliques and 3-anticliques are 3-universal
Nati Linial, Avraham Morgenstern
For given integers k, l we ask whether every large graph with a sufficiently small number of k-cliques and k-anticliques must contain an induced copy of every l-vertex graph. Here…
On the 3-local profiles of graphs
Hao Huang, Nati Linial, Humberto Naves +2
For a graph G, let p_i(G), i=0,...,3 be the probability that three distinct random vertices span exactly i edges. We call (p_0(G),...,p_3(G)) the 3-local profile of G. We investiga…
More Vertices of the Tristochastic Polytope
Nati Linial, Zur Luria, Maya Trakhtman
The doubly stochastic matrices constitute a polytope in , and by Birkhoff's theorem, its vertex set coincides with the set of order- permutation ma…
On high-dimensional acyclic tournaments
Nati Linial, Avraham Morgenstern
We study a high-dimensional analog for the notion of an acyclic (aka transitive) tournament. We give upper and lower bounds on the number of -dimensional -vertex acyclic tour…
Time to Cycle
Nir Lavee, Nati Linial
Consider the random process that starts with vertices and no edges, where the edges of are added one at a time in a uniformly chosen random order $e_1, e_2,\ldots, e_{\bi…
On the Rigidity of Sparse Random Graphs
Nati Linial, Jonathan Mosheiff
A graph with a trivial automorphism group is said to be rigid. Wright proved that for a random graph is rigid whp.…
Random simplicial complexes - around the phase transition
Nati Linial, Yuval Peled
This article surveys some of the work done in recent years on random simplicial complexes. We mostly consider higher-dimensional analogs of the well known phase transition in $G(n,…
Every Poset has a Large Cut
Nati Linial, Ori Shoshani
We prove that every finite poset has a directed cut with at least one half of the poset's pairwise order relations. The bound is tight. Also, the largest directed cut in a poset ca…
The threshold for collapsibility in random complexes
Lior Aronshtam, Nati Linial
In this paper we determine the threshold for collapsibility in the probabilistic model of -dimensional simplicial complexes. A lower bound for this threshold $p=\frac…
Musical chairs
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
In the {\em Musical Chairs} game a team of players plays against an adversarial {\em scheduler}. The scheduler wins if the game proceeds indefinitely, while terminati…
Clustering is difficult only when it does not matter
Amit Daniely, Nati Linial, Michael Saks
Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clu…
On the practically interesting instances of MAXCUT
Yonatan Bilu, Amit Daniely, Nati Linial +1
The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful…
Market Share Indicates Quality
Amir Ban, Nati Linial
Market share and quality, or customer satisfaction, go together. Yet inferring one from the other appears difficult. Indeed, such an inference would need detailed information about…
No justified complaints: On fair sharing of multiple resources
Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern +2
Fair allocation has been studied intensively in both economics and computer science, and fair sharing of resources has aroused renewed interest with the advent of virtualization an…
Geodesic Geometry on Graphs
Daniel Cizma, Nati Linial
We investigate a graph theoretic analog of geodesic geometry. In a graph we consider a system of paths where connects vertice…
Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones +2
A central and longstanding open problem in coding theory is the rate-versus-distance trade-off for binary error-correcting codes. In a seminal work, Delsarte introduced a family of…
Larger Corner-Free Sets from Better NOF Exactly- Protocols
Nati Linial, Adi Shraibman
A subset of the integer planar grid is called corner-free if it contains no triple of the form . It is known that such a set has a vanis…
Words Maps and Spectra of Random Graph Lifts
Nati Linial, Doron Puder
We begin with a new analysis of formal words. Let w be a formal word in letters g_1,...,g_k. The word map associated with w maps the permutations s_1,...,s_k in S_n to the permutat…
Strong Convergence in Posets
Amir Ban, Nati Linial
We consider the following solitaire game whose rules are reminiscent of the children's game of leapfrog. The player is handed an arbitrary ordering of the el…
On the Connectivity and Diameter of Geodetic Graphs
Asaf Etgar, Nati Linial
A graph is geodetic if between any two vertices there exists a unique shortest path. In 1962 Ore raised the challenge to characterize geodetic graphs, but despite many attempts…
How Balanced Can Permutations Be?
Gal Beniamini, Nir Lavee, Nati Linial
A permutation is -balanced if every permutation of order occurs in equally often, through order-isomorphism. In this paper, we explicitly construct…
On the weight distribution of random binary linear codes
Nati Linial, Jonathan Mosheiff
We investigate the weight distribution of random binary linear codes. For and pick uniformly at random vectors in and let $C \le \mathb…
Internal Partitions of Regular Graphs
Amir Ban, Nati Linial
An internal partition of an -vertex graph is a partition of such that every vertex has at least as many neighbors in its own part as in the other part. It has been…
Bounds on Unique-Neighbor Codes
Nati Linial, Edan Orzech
Recall that a binary linear code of length is a linear subspace . Here the parity check matrix is a binary matrix…
Expander Graphs -- Both Local and Global
Michael Chapman, Nati Linial, Yuval Peled
Let be a finite graph. For we denote by the subgraph of that is induced by 's neighbor set. We say that is -regular for integers,…
More data speeds up training time in learning halfspaces over sparse vectors
Amit Daniely, Nati Linial, Shai Shalev Shwartz
The increased availability of data in recent years has led several authors to ask whether it is possible to use data as a {\em computational} resource. That is, if more data is ava…
The Structure of Metrizable Graphs
Maria Chudnovsky, Daniel Cizma, Nati Linial
A consistent path system in a graph is an intersection-closed collection of paths, with exactly one path between any two vertices in . We call metrizable if every consis…
On the local profiles of trees
Sébastien Bubeck, Nati Linial
We study the local profiles of trees. We show that, in contrast with the situation for general graphs, the limit set of k-profiles of trees is convex. We initiate a study of the de…
On the Löwner-John Ellipsoids of the Metric Polytope
Raziel Gartsman, Nati Linial
The collection of all -point metric spaces of diameter constitutes a polytope , called the \emph{Metric Polytope}. In th…
On the Number of Path Systems
Daniel Cizma, Nati Linial
A path system in a graph is a collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is intersection-closed. W…
An Elementary Proof of the First LP Bound on the Rate of Binary Codes
Nati Linial, Elyassaf Loyfer
The asymptotic rate vs. distance problem is a long-standing fundamental problem in coding theory. The best upper bound to date was given in 1977 and has received since then numerou…
On the local structure of oriented graphs -- a case study in flag algebras
Shoni Gilboa, Roman Glebov, Dan Hefetz +2
Let be an -vertex oriented graph. Let (respectively ) be the probability that a random set of vertices of spans a transitive triangle (respectively an i…
Hyperpaths
Amir Dahari, Nati Linial
Hypertrees are high-dimensional counterparts of graph theoretic trees. They have attracted a great deal of attention by various investigators. Here we introduce and study Hyperpath…
Strictly Metrizable Graphs are Minor-Closed
Maria Chudnovsky, Daniel Cizma, Nati Linial
A consistent path system in a graph is an collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is intersecti…
Invariants of Random Knots and Links
Chaim Even-Zohar, Joel Hass, Nati Linial +1
We study random knots and links in R^3 using the Petaluma model, which is based on the petal projections developed by Adams et al. (2012). In this model we obtain a formula for the…
An approach to the girth problem in cubic graphs
Aya Bernstine, Nati Linial
We offer a new, gradual approach to the largest girth problem for cubic graphs. It is easily observed that the largest possible girth of all -vertex cubic graphs is attained by…
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable. There is presently a dearth of results showi…
A randomized construction of high girth regular graphs
Nati Linial, Michael Simkin
We describe a new random greedy algorithm for generating regular graphs of high girth: Let and be fixed. Let be even and set $g = c \log_…
Universal Knot Diagrams
Chaim Even-Zohar, Joel Hass, Nati Linial +1
We study collections of planar curves that yield diagrams for all knots. In particular, we show that a very special class called potholder curves carries all knots. This has implic…
On the densities of cliques and independent sets in graphs
Hao Huang, Nati Linial, Humberto Naves +2
Let r, s >= 2 be integers. Suppose that the number of blue r-cliques in a red/blue coloring of the edges of the complete graph K_n is known and fixed. What is the largest possible…
A note on Fermat's Last Theorem for
Matan Eliashar, Nati Linial
Fermat's Last theorem (FLT) famously states that the equation has no solution in positive integers for any integer exponent . But does this theorem hav…
Enumeration and randomized constructions of hypertrees
Nati Linial, Yuval Peled
Over thirty years ago, Kalai proved a beautiful -dimensional analog of Cayley's formula for the number of -vertex trees. He enumerated -dimensional hypertrees weighted by…
The Distribution of Knots in the Petaluma Model
Chaim Even-Zohar, Joel Hass, Nati Linial +1
The representation of knots by petal diagrams (Adams et al. 2012) naturally defines a sequence of distributions on the set of knots. In this article we establish some basic propert…
Extremal problems on shadows and hypercuts in simplicial complexes
Nati Linial, Ilan Newman, Yuval Peled +1
Let be an -vertex forest. We say that an edge is in the shadow of if contains a cycle. It is easy to see that if is "almost a tree", that is…
The complexity of learning halfspaces using generalized linear methods
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
Many popular learning algorithms (E.g. Regression, Fourier-Transform based algorithms, Kernel SVM and Kernel ridge regression) operate by reducing the problem to a convex optimizat…
Monotone Maps, Sphericity and Bounded Second Eigenvalue
Yonatan Bilu, Nati Linial
We consider {\em monotone} embeddings of a finite metric space into low dimensional normed space. That is, embeddings that respect the order among the distances in the original spa…
Efficient Generation of One-Factorizations through Hill Climbing
Maya Dotan, Nati Linial
It is well known that for every even integer , the complete graph has a one-factorization, namely a proper edge coloring with colors. Unfortunately, not much is kn…
Linear Programming Hierarchies in Coding Theory: Dual Solutions
Elyassaf Loyfer, Nati Linial
The rate vs. distance problem is a long-standing open problem in coding theory. Recent papers have suggested a new way to tackle this problem by appealing to a new hierarchy of lin…
Irreducible Non-Metrizable Path Systems in Graphs
Daniel Cizma, Nati Linial
A path system in a graph is said to be irreducible if there does not exist a partition such that restricts to a path system on…
Metric Approximations of Consistent Path Systems
Daniel Cizma, Nati Linial
A path system in a graph is a collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is cl…
On The Communication Complexity of High-Dimensional Permutations
Nati Linial, and Toniann Pitassi, Adi Shraibman
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) w…
The Rank-Ramsey Problem and the Log-Rank Conjecture
Gal Beniamini, Nati Linial, Adi Shraibman
A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our…
A King in every two consecutive tournaments
Yehuda Afek, Eli Gafni, Nati Linial
We think of a tournament as a communication network where in each round of communication processor sends its information to , for every directed edge $ij \i…
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes
Elyassaf Loyfer, Nati Linial
We develop a new family of linear programs, that yield upper bounds on the rate of binary linear codes of a given distance. Our bounds apply {\em only to linear codes.} Delsarte's…
On the number of 4-cycles in a tournament
Nati Linial, Avraham Morgenstern
If is an -vertex tournament with a given number of -cycles, what can be said about the number of its -cycles? The most interesting range of this problem is where i…
A Note on the Inducibility of 4-vertex Graphs
Chaim Even-Zohar, Nati Linial
There is much recent interest in understanding the density at which constant size graphs can appear in a very large graph. Specifically, the inducibility of a graph H is its extrem…
Triply Existentially Complete Triangle-Free Graphs
Chaim Even-Zohar, Nati Linial
A triangle-free graph G is called k-existentially complete if for every induced k-vertex subgraph H of G, every extension of H to a (k+1)-vertex triangle-free graph can be realized…