IC Colloquium : Signrank and its applications in combinatorics and complexity
Event details
| Date | 26.09.2016 |
| Hour | 16:15 › 17:30 |
| Location | |
| Category | Conferences - Seminars |
By: Noga Alon - Tel Aviv University
Video of his talk: http://slideshot.epfl.ch/play/icc_alon
Abstract:
The sign-rank of a real matrix A with no 0 entries is the minimum rank of a matrix B so that A_{ij}B_{ij} >0 for all i,j. The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic and describe its background, several recent results from joint work with Moran and Yehudayoff, and some intriguing open problems.
Bio:
Noga Alon is a Baumritter Professor of Mathematics and Computer Science in Tel Aviv University, Israel. He received his Ph. D. in Mathematics at the Hebrew University of Jerusalem and has been multiple times a visiting professor in the Institute for Advanced Study in Princeton. Since 2009 he is also a member of Microsoft Research, Israel.
His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry and Combinatorial Number Theory.
He published more than five hundred research papers and is a member of the Israel Academy of Sciences and of the Academia Europaea. He received the
Erdos Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Goedel Prize, the Israel Prize, the EMET Prize,
the Dijkstra Prize and Honorary Doctorates from ETH Zurich and from the University of Waterloo.
More information
Video of his talk: http://slideshot.epfl.ch/play/icc_alon
Abstract:
The sign-rank of a real matrix A with no 0 entries is the minimum rank of a matrix B so that A_{ij}B_{ij} >0 for all i,j. The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic and describe its background, several recent results from joint work with Moran and Yehudayoff, and some intriguing open problems.
Bio:
Noga Alon is a Baumritter Professor of Mathematics and Computer Science in Tel Aviv University, Israel. He received his Ph. D. in Mathematics at the Hebrew University of Jerusalem and has been multiple times a visiting professor in the Institute for Advanced Study in Princeton. Since 2009 he is also a member of Microsoft Research, Israel.
His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry and Combinatorial Number Theory.
He published more than five hundred research papers and is a member of the Israel Academy of Sciences and of the Academia Europaea. He received the
Erdos Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Goedel Prize, the Israel Prize, the EMET Prize,
the Dijkstra Prize and Honorary Doctorates from ETH Zurich and from the University of Waterloo.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: N. Vishnoi