• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Contacts

Dean — Ivan Arzhantsev

 

First Deputy Dean— Tamara Voznesenskaya

 

Deputy Dean for Research and International Relations - Sergei Obiedkov

 

Deputy Dean for finance and administration - Irina Plisetskaya

 

Dean's office
 

Phone: +7 (495) 772-95-90 * 12332

computerscience@hse.ru

Moscow, 3 Kochnovsky Proezd (near metro station 'Aeroport'). 

Colloquium

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 Thursdays in the Faculty of Computer Science building at 3 Kochnovsky Proezd, lecture hall Descartes on floor 3.

NB: a somewhat more detailed web page is available in Russian here.

Registration for the Colloquium is open: computerscience@hse.ru 

2017 – 2018

November 28, 16:40 – 18:00 

Vladimir Kolmogorov, IST Austria

Complexity Classifications of Valued Constraint Satisfaction Problems

Classifying complexity of different classes of optimization problems is an important research direction in Theoretical Computer Science. One prominent framework is Valued Constraint Satisfaction Problems (VCSPs) in which the class is parameterized by a "language", i.e. a set of cost functions over a fixed discrete domain. An instance of the problem is an arbitrary sum of functions from the language (possibly with overlapping variables), with the goal to minimize the sum. This framework can capture many classes of optimization problems such as 3-SAT, graph coloring, minimum vertex cover, submodular minimization, and others.

A series of recent papers, culminating with the works of D. Zhuk and A. Bulatov in 2017, has established a complete complexity classification of arbitrary languages. I will describe our contributions to this topic. One of the results is a reduction from general VCSPs to plain CSPs (i.e. to languages with {0, infinity}-valued functions). The key algorithmic tool that we use is a certain LP relaxation of the problem combined with the algorithm for plain CSPs.

In the second part of the talk, I will consider a version of the CSP framework where each variable must appear in exactly two constraints. It captures, in particular, the class of perfect matching problems, which can be solved by the Edmonds's blossom-shrinking algorithm. I will present a generalization of this algorithm that can handle "even Delta-matroid constraints". As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec.

Colloquium

Venue:

Moscow, Kochnovsky pr.,3, room 205, 16:40 
Everyone interested is welcome to attend. 
If you need a pass to HSE, please contact computerscience@hse.ru


November 28,18:10 – 19:30 

Andrea Burattin, DTU, Denmark

Online Process Mining

Process mining analyses data referring to executions of (business) processes. Typical approaches analyse historical execution data post-hoc, while online process mining aims at inferring information for running executions based "live data". Online mining carries scientific and computational challenges, since the processing has to take place immediately when events are emitted, possibly at very high speed. The benefits, however, are very relevant: online mining provides immediate knowledge on what is happening, thus detecting very early if the system is properly behaving and how its users interact with it. In this talk we focus on the online discovery of processes and how they evolve over time. Secondly, we present online conformance checking: detecting if – and to what extent – running executions are deviating from the reference behaviour they are supposed to follow.

Colloquium

Venue:

Moscow, Kochnovsky pr.,3, room 205, 18:10 
Everyone interested is welcome to attend.  
If you need a pass to HSE, please contact computerscience@hse.ru


September 11, 18:10 – 19:30 

Wray Buntine, Monash University

Learning on networks of distributions for discrete data

I will motivate the talk by reviewing some state of the art models for problems like matrix factorisation models for link prediction and tweet clustering. Then I will review the classes of distributions that can be strung together in networks to generate discrete data. This allows a rich class of models that, in its simplest form, covers things like Poisson matrix factorisation, Latent Dirichlet allocation, and Stochastic block models, but, more generally, covers complex hierarchical models on network and text data. The distributions covered include so-called non-parametric distributions such as the Gamma process. Accompanying these are a set of collapsing and augmentation techniques that are used to generate fast Gibbs samplers for many models in this class. To complete this picture, turning complex network models into fast Gibbs samplers, I will illustrate our recent methods of doing matrix factorisation with side information (e.g., GloVe word embeddings), done for link prediction, for instance, for citation networks.

Colloquium

Venue:

Moscow, Kochnovsky pr.,3, room 317, 18:10
Everyone interested is welcome to attend.
If you need a pass to HSE, please contact computerscience@hse.ru

Сolloquium in 2016/2017

Сolloquium in 2015/2016