Computer Science Faculty Hosts Conference on Theoretical Computer Science

On June 14 the workshop ‘Complexity of Computation, Communication, Descriptions, and Proofs’, organized by the Laboratory of Theoretical Computer Science, was held at HSE Faculty of Computer Sciences. The conference was organized as part of the major international conference ‘Computer Science in Russia’.

Several reports on coding theory, proof complexity, communication complexity, the complexity of tree-like resolutions, and algorithm theory were presented at the event. The reports were intended for participants with basic knowledge of theoretical computer science.

Leading Russian and international researchers presented their reports at the workshop.

Amnon Ta-Shma (Tel-Aviv University) spoke on ‘Explicit, almost optimal, eps-balanced codes’.

Bruno Loff (University of Porto) presented his research ‘Communication vs query complexity, new results’.

Stephen Fenner (The University of South Carolina) talked on ‘Geometric approaches to derandomizing parallel matching and matroid algorithms’.

Dmitry Sokolov (Steklov Institute of Mathematics, Russian Academy of Sciences, St Petersburg) delivered a report on ‘Monotone interpolation in proof complexity’.

Grigory Yaroslavtsev (Indiana University, Bloomington) spoke on ‘Computational and communication complexity in massively parallel computing’.

For more information about the event please see the workshop website.

Lab staff members also organized two mini courses  ‘Asymmetric Communication Complexity’ and ‘The matching problem: Approaches, applications, and algorithms’ delivered by Bruno Loff and Stephen Fenner. 

The video of the courses is available on Youtube and Vkontakte.