Nati Linial

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 27

Top Topics

Linear Programming

Average Case Complexity

Top Venues

J. Graph Theory

Random Struct. Algorithms

Discret. Comput. Geom.

Publications

Gal Beniamini, Nati Linial, Adi Shraibman
The Rank-Ramsey Problem and the Log-Rank Conjecture. CoRR (2024)
Asaf Etgar, Nati Linial
On the connectivity and diameter of geodetic graphs. Eur. J. Comb. 116 (2024)
Daniel Cizma, Nati Linial
Irreducible nonmetrizable path systems in graphs. J. Graph Theory 102 (1) (2023)
Elyassaf Loyfer, Nati Linial
New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes. IEEE Trans. Inf. Theory 69 (5) (2023)
Nati Linial, Elyassaf Loyfer
An Elementary Proof of the First LP Bound on the Rate of Binary Codes. CoRR (2023)
Nati Linial, Idan Orzech
Bounds on Unique-Neighbor Codes. CoRR (2022)
Elyassaf Loyfer, Nati Linial
Linear Programming Hierarchies in Coding Theory: Dual Solutions. CoRR (2022)
Shoni Gilboa, Roman Glebov, Dan Hefetz, Nati Linial, Avraham Morgenstern
On the Local Structure of Oriented Graphs - a Case Study in Flag Algebras. Electron. J. Comb. 29 (3) (2022)
Daniel Cizma, Nati Linial
Geodesic Geometry on Graphs. Discret. Comput. Geom. 68 (1) (2022)
Elyassaf Loyfer, Nati Linial
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes. CoRR (2022)
Nati Linial, Michael Simkin
A randomized construction of high girth regular graphs. Random Struct. Algorithms 58 (2) (2021)
Nati Linial, Adi Shraibman
An Improved Protocol for the Exactly-N Problem. Computational Complexity Conference (2021)
Michael Chapman, Nati Linial, Yuval Peled
Expander Graphs - Both Local and Global. Comb. 40 (4) (2020)
Amir Dahari, Nati Linial
Hyperpaths. CoRR (2020)
Nati Linial, Jonathan Mosheiff
On the weight distribution of random binary linear codes. Random Struct. Algorithms 56 (1) (2020)
Nati Linial, Toniann Pitassi, Adi Shraibman
On the Communication Complexity of High-Dimensional Permutations. ITCS (2019)
Yehuda Afek, Eli Gafni, Nati Linial
A King in every two consecutive tournaments. CoRR (2019)
Michael Chapman, Nati Linial, Yuval Peled
Expander Graphs - Both Local and Global. FOCS (2019)
Nati Linial, Yuval Peled
Enumeration and randomized constructions of hypertrees. Random Struct. Algorithms 55 (3) (2019)
Nati Linial, Jonathan Mosheiff
On the weight distribution of random binary linear codes. CoRR (2018)
Nati Linial, Adi Shraibman
On The Communication Complexity of High-Dimensional Permutations. CoRR (2017)
Nati Linial, Jonathan Mosheiff
On the Rigidity of Sparse Random Graphs. J. Graph Theory 85 (2) (2017)
Amir Ban, Nati Linial
Internal Partitions of Regular Graphs. J. Graph Theory 83 (1) (2016)
Nati Linial, Avraham Morgenstern
On the Number of 4-Cycles in a Tournament. J. Graph Theory 83 (3) (2016)
Chaim Even-Zohar, Joel Hass, Nati Linial, Tahl Nowik
Invariants of Random Knots and Links. Discret. Comput. Geom. 56 (2) (2016)
Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, Benny Sudakov
On the densities of cliques and independent sets in graphs. Comb. 36 (5) (2016)
Sébastien Bubeck, Nati Linial
On the Local Profiles of Trees. J. Graph Theory 81 (2) (2016)
Nati Linial, Avraham Morgenstern
Graphs with Few 3-Cliques and 3-Anticliques are 3-Universal. J. Graph Theory 78 (3) (2015)
Chaim Even-Zohar, Nati Linial
Triply Existentially Complete Triangle-Free Graphs. J. Graph Theory 78 (4) (2015)
Nati Linial, Jonathan Mosheiff
On the Rigidity of Sparse Random Graphs. CoRR (2015)
Chaim Even-Zohar, Nati Linial
A Note on the Inducibility of 4-Vertex Graphs. Graphs Comb. 31 (5) (2015)
Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, Benny Sudakov
On the 3-Local Profiles of Graphs. J. Graph Theory 76 (3) (2014)
Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
Musical Chairs. SIAM J. Discret. Math. 28 (3) (2014)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
From average case complexity to improper learning complexity. STOC (2014)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
The Complexity of Learning Halfspaces using Generalized Linear Methods. COLT (2014)
Amir Ban, Nati Linial
Market Share Indicates Quality. CoRR (2014)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
More data speeds up training time in learning halfspaces over sparse vectors. NIPS (2013)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
From average case complexity to improper learning complexity. CoRR (2013)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
More data speeds up training time in learning halfspaces over sparse vectors. CoRR (2013)
Nati Linial, Avraham Morgenstern
On High-Dimensional Acyclic Tournaments. Discret. Comput. Geom. 50 (4) (2013)
Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
On the practically interesting instances of MAXCUT. STACS (2013)
Amir Ban, Nati Linial
Strong convergence in posets. J. Comb. Theory, Ser. A 119 (6) (2012)
Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
Musical chairs CoRR (2012)
Amit Daniely, Nati Linial, Michael E. Saks
Clustering is difficult only when it does not matter CoRR (2012)
Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
On the practically interesting instances of MAXCUT CoRR (2012)
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
The error rate of learning halfspaces using Kernel-SVMs CoRR (2012)
Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
Oblivious Collaboration. DISC (2011)
Amir Ban, Nati Linial
The dynamics of reputation systems. TARK (2011)
Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, Nati Linial
No justified complaints: On fair sharing of multiple resources CoRR (2011)
Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
Oblivious Collaboration CoRR (2011)
Nati Linial, Doron Puder
Word maps and spectra of random graph lifts. Random Struct. Algorithms 37 (1) (2010)
Nati Linial, Adi Shraibman
Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms 34 (3) (2009)
Nati Linial, Adi Shraibman
Learning Complexity vs. Communication Complexity. Computational Complexity Conference (2008)
Nati Linial, Adi Shraibman
Lower bounds in communication complexity based on factorization norms. STOC (2007)
Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman
Complexity measures of sign matrices. Comb. 27 (4) (2007)