Publications (29)
Oblivious Collaboration
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
More data speeds up training time in learning halfspaces over sparse vectors
Amit Daniely, Nati Linial, Shai Shalev Shwartz
Graphs with few 3-cliques and 3-anticliques are 3-universal
Nati Linial, Avraham Morgenstern
On the local profiles of trees
Sébastien Bubeck, Nati Linial
On the 3-local profiles of graphs
Hao Huang, Nati Linial, Humberto Naves +2
On high-dimensional acyclic tournaments
Nati Linial, Avraham Morgenstern
On the Rigidity of Sparse Random Graphs
Nati Linial, Jonathan Mosheiff
Random simplicial complexes - around the phase transition
Nati Linial, Yuval Peled
Invariants of Random Knots and Links
Chaim Even-Zohar, Joel Hass, Nati Linial +1
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
The threshold for collapsibility in random complexes
Lior Aronshtam, Nati Linial
Musical chairs
Yehuda Afek, Yakov Babichenko, Uriel Feige +3
On the densities of cliques and independent sets in graphs
Hao Huang, Nati Linial, Humberto Naves +2
Enumeration and randomized constructions of hypertrees
Nati Linial, Yuval Peled
The Distribution of Knots in the Petaluma Model
Chaim Even-Zohar, Joel Hass, Nati Linial +1
Clustering is difficult only when it does not matter
Amit Daniely, Nati Linial, Michael Saks
Extremal problems on shadows and hypercuts in simplicial complexes
Nati Linial, Ilan Newman, Yuval Peled +1
The complexity of learning halfspaces using generalized linear methods
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
Monotone Maps, Sphericity and Bounded Second Eigenvalue
Yonatan Bilu, Nati Linial
On the practically interesting instances of MAXCUT
Yonatan Bilu, Amit Daniely, Nati Linial +1
Market Share Indicates Quality
Amir Ban, Nati Linial
Efficient Generation of One-Factorizations through Hill Climbing
Maya Dotan, Nati Linial
No justified complaints: On fair sharing of multiple resources
Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern +2
On The Communication Complexity of High-Dimensional Permutations
Nati Linial, and Toniann Pitassi, Adi Shraibman
Words Maps and Spectra of Random Graph Lifts
Nati Linial, Doron Puder
On the number of 4-cycles in a tournament
Nati Linial, Avraham Morgenstern
A Note on the Inducibility of 4-vertex Graphs
Chaim Even-Zohar, Nati Linial
Triply Existentially Complete Triangle-Free Graphs
Chaim Even-Zohar, Nati Linial
Internal Partitions of Regular Graphs
Amir Ban, Nati Linial