Local Combinatorics, and Some Words on Local-to-Global Phenomena
Fix a (small) integer k and let G be a graph. For every set of k vertices in G we consider the subgraph induced by it. This distribution on k-vertex graphs is called the k-profile of G. Our two main questions are: (i) What are possible k-profiles of large graphs?
- What global properties of G can be deduced from knowledge of its profiles? Recent progress in the domain of graph limits suggests that problem (i) is key to the study of general families of random graphs.
This in turn may prove useful in investigating big data that comes in the form of large graphs (e.g., in bioinformatics). The most outstanding open question of type (ii) is the Erdos Hajnal conjecture which posits that for every graph H there is an epsilon 0, such that in every n-vertex G which contains no induced copy of H either the clique number or the anticlique number is nε. Several open questions will be mentioned in this talk. The new results that I will present are joint with Yuval Peled, Avraham Morgenstern, Benny Sudakov, Hao Huang and Humberto Naves
References
[1] The geometry of graphs and some of its algorithmic applications N Linial, E London, Y Rabinovich – Combinatorica, 1995 – Springer; cited by 786
[2] Expander graphs and their applications S Hoory, N Linial, A Wigderson – Bulletin of the American Mathematical Soc., 2006 – Cited by 631
[3] Constant depth circuits, Fourier transform, and learnability N Linial, Y Mansour, N Nisan – Journal of the ACM (JACM), 1993; Cited by 484
[4] The influence of variables on Boolean functions J Kahn, G Kalai, N Linial – Foundations of Computer Science 1988 – Cited by 416
Speaker Details
Nati Linial is a Professor at the School of Computer Science and Engineering at the Hebrew University of Jerusalem. He is well known for many influential advances on the interface of Combinatorics and Computer Science. His most cited contributions include [1]-[4] below.
For more information, see http://www.cs.huji.ac.il/~nati/
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Nati Linial
- Affiliation:
- Hebrew University
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-