Colloquium 2019/2020
For a researcher in a diverse and quickly developing area of knowledge such as computer science, it is important to maintain a broad perspective and strive to understand what colleagues in related fields are studying. This requires a platform where specialists can meet and tell each other about their latest findings in a common language. Such a platform is the Colloquium of HSE's Faculty of Computer Science. This platform is a faculty-wide academic seminar designed for teachers and research staff, graduate and undergraduate students, as well as those who are interested in computer science.
Colloquium meetings are held on Tuesdays in the Faculty of Computer Science building at Kochnovsky Proezd, 3, lecture hall 205, 2nd floor.
NB: a somewhat more detailed web page is available in Russian here.
Date: February 18, 18:10 – 19:30
Placе: Pokrovsky blvd 11, room R503
Title: Of Points and Lines: Graphs, Metrics, and Betweenness
Speaker: Laurent Beaudou (HSE)
Abstract: Given n points in the Euclidean plane, they are either all collinear or define at least n distinct lines. This result is a corollary of the Sylvester-Gallai theorem. Its combinatorial generalization was proven by de Bruijn and Erdös in the forties. In 2008, Chen and Chvátal described a generalization of the notion of a line to any metric space and conjectured that the same result remains true in that framework. Since then, a growing community of researchers has been investigating this question. It remains open for metric spaces and even for those specific metric spaces generated by graphs. In this talk, we shall see a broad overview of the state of research on the matter: results and (many!) remaining open questions.
Date: December 15, 16:20 – 17:40
Placе: Pokrovsky blvd 11, room R503
Title: On robust mean estimation and k-means clustering
Speaker: Nikita Zhivotovskiy, Google research
Abstract: In this talk we consider the robust algorithms for the k-means clustering problem where a quantizer is constructed based on N independent observations. We start with an overview of the methods of robust statistics. First, we discuss the median-of-means estimator. This simple estimator allows us to evaluate the mean of some heavy-tailed distribution as if this distribution was Gaussian. We discuss some extensions to the multivariate case. In the context of clustering, we present the median of means based non-asymptotic distortion bounds that hold under the two bounded moments assumption. In particular, our results extend the renowned asymptotic result of Pollard who showed that the existence of two moments is dsufficient for strong consistency of an empirically optimal quantizer in R. In a special case of clustering in Rd, under two bounded moments, we show matching non-asymptotic upper and lower bounds on the distortion, which depend on the probability mass of the lightest cluster of an optimal quantizer. This talk is based mainly on the joint work with Y. Klochkov and A. Kroshnin to appear in Annals of Statistics).
Colloquium (PDF, 441 Kb)
Date: November 12, 16:40 – 18:00
Placе: Pokrovsky blvd 11, room R503
Title: Some Adventures in Boolean Satisfiability and Its Logic Synthesis Applications
Speaker: Jie-Hong Roland Jiang (National Taiwan University)
Abstract: Boolean satisfiability (SAT) is a fundamental NP-complete problem. Its general and simple formulation makes it an ideal problem to tackle. Although SAT is intractable, many efficient solvers have been engineered and widely applied in industries. This talk will introduce some of the key enabling techniques in SAT solving and showcase some applications in logic synthesis.
Date: September 10, 16:40 – 18:00
Placе: Pokrovsky blvd 11, room R503
Title: From Theorem Proving to Cognitive Reasoning)
Speaker: Ulrich Furbach, University of Koblenz and wizAI GmbH
Abstract: Starting from a depiction of the state of the art in predicate logic theorem proving we address problems which occur if provers are applied in the wild. In particular we discuss how automated reasoning systems can be used for natural language question answering. Our approach to take common sense reasoning benchmarks within the Corg project is presented and we demonstrate how word embeddings can help with the problem of axiom selection.