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

Seminar of the laboratory

The main aim of the seminar is to discuss both new and classical results in Theoretical Computer Science.

The seminar is held weekly. The recurring topic for the Fall 2016 is "Boolean Fourier Analysis". The information on the talks is given below.

The seminar is held at the Department of Computer Science in HSE on Wednesdays from 18:10 to 19:30 in the room 503.

To attend the seminar you need a pass to the building. If you don’t have a pass please send your contact information (Surname, name) to Dina Chernyshova: dchernyshova@hse.ru

Peter Gacs 

Khaled Elbassioni "Some Applications of the Multiplicative Weights Update Method in (Semi) Infinite (Discrete) Optimization"

Kazuhisa Makino "The complexity issues on stochastic games"

April 03,2019
Ranko Lazic 
«Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games»

October 10, 2018
Vadim Griberg 
«LP-based approximation of Minimum k-Star Cover»

October 03, 2018
 Alexander Kozachinskiy 
«Data structures for polynomial evaluation»


V.Podolskii “Complexity of dense linear operators”

September 19, 2018
Michael Raskin 
«Clique-width based graph algorithms»

September 12, 2018
D Dagaev, A. Suzdaltsev «Optimality of seedings in knock-out tournaments»

June 20, 2018
D. Chistikov 
«On the complexity of quantified integer programming»

June 13, 2018

D. Chistikov «Navigating one-counter automata: Directions in the mountains»

May 30, 2018
G. Evsropov «The k-sum metric combinatorial optimization problem»

May 23, 2018
G. Posobin «Random noise increases Kolmogorov complexity»

May 5, 2018
A. Romashchenko «Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts»

April 11, 2018
V. Grinberg «Sum-of-squares optimization for polynomials»

April 04, 2018
Y. Nesterov «Implementable Tensor Methods in Unconstrained Convex Optimization»

March 21, 2018
A. Milovanov «PIT derandomization and generalization of Sylvester–Gallai theorem»

March 07, 2018
A. Rubtsov 
«Exile of Kolmogorov Complexity from KC-DCF-Lemma»

February 14, 2018

V. Grinberg «L0-sampling and graph sketches»

February 07, 2018
Vladimir Podolskii «A game approach to the sensitivity conjecture»

January 24, 2018
Ekaterina Mineeva «Parameterized Complexity»

December 13, 2017
Michael Raskin «Complementing unambiguous finite automata (a superpolynomial lower bound for 1-letter alphabet)»

November 22, 2017
Guilhem Gamard «Quasiperiodicity on one and two-dimensional words. Continuation of previous talk: two-dimensional aspects»

November 08, 2017
Alexander Shen   «Geometric constructions and its non-existence»

November 01, 2017
Guilhem Gamard  «Quasiperiodicity on one and two-dimensional words»

October 18, 2017
V. Chernyshev 
«Point dynamics on metric graphs»

October 11, 2017
Y. Makarychev «Algorithmic and Hardness Results for the Hub Labeling Problem»

October 03, 2017
K. Makarychev  «Clustering Billions of Reads for DNA Data Storage»

May 31, 2017
T. Iskhakov «A brief introduction to the flow algorithms»

May 24, 2017
S. Kuznetsov «Categorial grammar: logical-mathematical approach to the description of natural language»

May 10, 2017
M. Vyalyi  «Nonnegative and PSD matrix ranks and their connection with classical and quantum communication» 

April 4, 201A. Ryazanov «The upper bound for mutual information by the rank of matrix for joint distribution»

April 12-19, 2017
M. Kaledin «Applications of Gröbner basis for integer programming» 

April 5, 2017
V. Podolskii «About STACS 2017»

March 15-22, 2017
M. Vyalyi «Fine-grained reductions»

March 9, 2017
A. Knop «Time hierarchy theorems for heuristic computations»

February 22 - March 3, 2017
G. Evstropov «Optimal algorithms for solving some zero-sum games with ordered sets of coins»

February 15, 2017
D. Kutenin «A polynomial algorithm for primality testing»

January 25 – February 1, 2017
M. Vyalyi  «A quasipolynomial algorithm for solving parity games»

January 11, 2017
Tomislav Petrović «A step towards finding an infinite string which is neither random nor predictable»

December 7, 2016
K. Makarychev «Solving Optimization Problems with Diseconomies of Scale»

December 9-16, 2016
A. Shen  «On normal sequences»

November 2, 2016
V. Oparin «The bounds of proof complexity in the proof systems based on the resolution method»

October 19, 2016
A. Skopenkov «Stability of intersections of graphs in the plane and the van Kampen obstruction»

September 23 – October 12, 2016
G. Posobin, V. Podolskii, A. Milovanov, M. Vyalyi «Basic concepts of the Fourier analysis of Boolean functions»






Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!
To be used only for spelling or punctuation mistakes.