2015 Stanisław Łojasiewicz Lecture

Preparatory Workshop

Kraków, 6 May 2015 (Wednesday)

Schedule

10.00-10.45

 Grzegorz Gutowski (UJ) Learnability and the Vapnik-Chervonenkis Dimension I

Abstract: Computational Learning Theory is a sub-area of Theoretical Computer Science that seeks to design efficient and provably correct algorithms for natural learning tasks and to rigorously establish why some other learning tasks are inherently intractable. A central computational model of learning was introduced by Valiant in 1984 and is known as PAC (Probably Approximately Correct) model. We will give a short introduction to this model explaining its relations to sign matrices and the Vapnik-Chervonenkis dimension.
 

10.45-11.15

 Coffee break
 

11.15-12.00

 Grzegorz Gutowski (UJ) Learnability and the Vapnik-Chervonenkis Dimension II
 

12.15-13.00

Bartłomiej Bosek (UJ) Real Varieties and Sign Patterns of Polynomials

Abstract: We will present some combinatorial applications of theorems of Milnor and Warren concerning the number of connected components of real varieties. One of them is a result of Alon and Scheinerman on dimension of containment orders. Another one is a theorem of Alon concerning the number of order types of point configurations in Euclidean spaces.

13.00-14.00

 Lunch break

14.00-14.45

 Maciej Gawron (UJ) Communication Complexity I

Abstract: We will give a short introduction to Communication Complexity, an important sub-area of Complexity Theory dealing with problems of the following type. Suppose that Alice and Bob are given positive integers x and y, respectively. What is the least amount of information needed for them to find out whether these numbers are equal or not? We will review basic communication models together with classical results and challenging open problems, including the famous Log-Rank Conjecture.
 

15.00-15.45

 Jarosław Grytczuk (UJ) Communication Complexity II

Abstract: We will focus on probabilistic communication models. Besides some basic results, we will present spectacular achievements, like a theorem of Paturi and Simon relating communication complexity to hyperplane arrangements, or a theorem of Forster giving a lower bound for the sign rank of Hadamard matrices. Connection of sign rank to the famous Sensitivity Conjecture will be mentioned.
 


All lectures will take place in Room 1016 of the Department of Mathematics and Computer Science of Jagiellonian University (New Campus, Kraków).

Please contact Jarosław Grytczuk for further details.