# 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 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

19.06.2019

Peter Gacs "Eroders"

This talk is about cellular automata on a finite-dimensional lattice---a certain kind that has special interest for error correction. A state 0 is distinguished, and a cellular automaton is called an "eroder'' if it eliminates any finite island of non-0s. We restrict attention to cellular automata whose state set is ordered with 0 being minimal, and whose transition rule is monotonic. (For example majority vote over some neighbors.) A classical result of Toom characterizes all 2-state eroders (in any dimension). It also shows that such eroders erode in linear time, and resist (low random) noise. (The latter was key to building the simplest known construction of a reliable computation model.)

Here I will report on work (some of it old by Galperin and Toom, some of it new, joint with Ilkka Törmä and Mathieu Hilaire) trying to extend these results to more than 2 states. In one dimension, all eroders erode in linear time, but not all resist noise. In 2 dimensions and 3 states, some eroders need more than linear time, and we don't even know whether the eroder property is decidable. Characterizing eroders that resist noise (in any dimension) seems easier than to characterize just eroders (they all erode in linear time).

07.06.2019

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

Standard (continuous or discrete) optimization problems typically assume that the dimension and the number of constrains in the problem are finite. In many practical situations, either one or both of these two parameters may be infinite. Examples include: (i) the art gallery problem from computational geometry, where it is required to guard the infinite set of points of an art gallery with the minimum number of cameras, and (ii) robust optimization problems, in which the coefficients of the constraints and/or the objective function are drawn from some infinite uncertainty sets, and the goal is to solve the optimization problem for the worst-case choice in each uncertainty set. In this talk, we highlight some of these examples, and then describe how the well-known multiplicative weights update method can be applied to derive efficient approximation algorithms for solving this type of problems.

05.06.2019

Kazuhisa Makino "The complexity issues on stochastic games"

Stochastic games were introduced in 1953 by Shapley for the discounted case, and extended to the undiscounted case in 1957 by Gillette. Each such game is a dynamic game with probabilistic transitions played by two players on a finite set of states. The game is played in the infinite sequence of rounds. In the round, the game is in some state. The players choose actions. Then they receive payoffs and the game moves to a new random state, where the payoffs and the transition probability depend on the previous state and the actions chosen by the players. The procedure is repeated at the new state. Stochastic games generalize parity games, cyclic games, simple stochastic games, and BWR games, which all belong to NP and coNP, but are not known to be solved in polynomial time. In this talk, I briefly survey the algorithmic issues on these games, as well as the properties on the optimal strategies for them. I also discuss recent works obtained with Endre Boros, Khaled Elbassioni, and Vladimir Gurvich.

24.04.2019

A. Rubtsov "Automata with additional data structures"

in Russian

17.04.2019

V.Podolskii "Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits"

in Russian

10.04.2019

A. Romashchenko " How to use undiscovered entropy inequalities"

in Russian

03.04.2019

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

Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games, a key technical component of which is constructing (explicitly or implicitly) an automaton that separates languages of words encoding plays that are (decisively) won by either of the two players. Our main technical result is a quasi-polynomial lower bound on the size of such separating automata that nearly matches the current best upper bounds. This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games. The key and fundamental concept that we introduce and study is a universal ordered tree. The technical highlights are a quasi-polynomial lower bound on the size of universal ordered trees and a proof that every separating safety automaton has a universal tree hidden in its state space.

20.03.2019

D. Taletskiy " Investigation of the number of maximum and largest independent sets in some classes of trees "

in Russian

13.03.2019

D. Zhuk " The complexity of the task of satisfying the constraints depending on the language of the constraints "

in Russian

06.03.2019

A. Milovanov" Turing machine games and the power of random strings "

in Russian

27.02.2019

A. Storozhenko" Lower test scores for dicotry through communication complexity "

in Russian

30.01.2019

D.Sirotkin " Investigation of the computational complexity of the problems of an independent set and a vertex k-coloring in some classes of graphs"

in Russian

16.01.2019

I. Arzhantsev " Theory of divisors and combinatorics in a free semigroup "

in Russian

10.10.2018

V. Grinberg "LP-based approximation of Minimum k-Star Cover"

Consider the following problem: we are given two sets in a metric space, facilities and clients, and an integer k. A star is a pair of one facility and a subset of clients assigned to this facility, and the weight of a star is sum of distances from the facility to assigned clients. We need to select a subset of at most k facilities and assign every client to exactly one of the selected facilities, creating stars, so that the maximal weight of a star (over all stars created) is minimal. This problem is NP-hard, and in spite of resembling k-Facility Location, k-Median or their capacitated versions, it is one of the most poorly studied problems of that kind.

My talk will be devoted to approximation algorithm, based on standard LP relaxation. I will show that, unless we are allowed to violate the number k of opened stars, the integrality gap of standard LP is unbounded, and if we can open at most (1 + eps)k stars, it is Omega(1/eps), for any eps > 0. I will also present a polynomial time approximation algorithm, which opens at most (1 + eps)k stars, and the cost of the returned solution is no worse than O(1/eps^2) times the true (unrelaxed) optimum.

03.10.2018

Alexander Kozachinskiy "Data structures for polynomial evaluation".

The talk will be devoted to the polynomial evaluation problem. We are given an univariate polynomial of degree at most n with coefficients in some finite field and we want to answer queries of the form: for a point in a field, what is the value of our polynomial on this point? I will present a lower bound of Larsen which states that for data structures of size linear in n query time should be at least logarithmic in n. This is the strongest known lower bound for static data structures.

I will also give an upper bound of Kedlaya and Umans. They constructed a data structure for polynomial evaluation of size nearly linear in n with polylogarithmic query time.

26.09.2018

V.Podolskii “Complexity of dense linear operators”

Suppose we have a vector x of n Boolean variables and we want to compute a Boolean operator Ax with Boolean square matrix A. That is, for all rows of A we would like to compute an OR of variables of x that has ones in the corresponding coordinate of the row. We start with variables and in one step we are allowed to apply OR operation to two expressions computed on previous steps (we build a circuit consisting of OR gates).

If A is a sparse matrix (has O(n) ones), this can easily be done in O(n) operations. We show that the same is true for very dense matrices (O(n) zeros).

This result translates to computation of operators over arbitrary commutative semiring. We also show that that the same cannot be done for semirings with large enough amount of non-commutativity.

19.09.2018

Michael Raskin "Clique-width based graph algorithms"

Many graph problems (for example, checking 3-colourability) are known to be NP-complete. But it turns out that they are fixed-parameter tractable, i.e. there are notions of graph structural complexity such that many problems are easy even for large graphs with low complexity.

In the talk, I will explain the notion of clique-width of the graph and show how to optimise a term-automata-based colouring algorithm based on the clique-width representation for counting the colourings with large number of colours.

12.09.2018

D. Dagaev, A. Suzdaltsev "Optimal seeding in knockout tournaments".

in Russian

20.06.2018

D. Chistikov "On the complexity of quantified integer programming".

Quantified integer programming is the problem of deciding assertions of the form "for all/there exists x_k ... for all x_2 there exists x_1 such that A x >= c", where vectors of variables x_k, ..., x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes.

We show that quantified integer programming with alternation depth k is complete for the k-th level of the polynomial hierarchy.

Joint work with Christoph Haase.

13.06.2018

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

One-counter automata (OCA) are finite-state automata with a counter that supports increments, decrements, and tests for zero. They correspond to an intermediate class between regular and context-free languages and are suitable for modeling ``counting'' phenomena. However, reasoning about OCA is often intractable: for example, language equivalence is undecidable for nondeterministic OCA, and for deterministic OCA it took 40 years to prove the existence of short distinguishing words.

In this talk, I will give a review of OCA and reasoning tasks for them and discuss two tractability results:

(1) shortest paths between configurations of OCA are of at most quadratic length;

(2) the Parikh (commutative) image and sub-/superword closures of the language are accepted by small nondeterministic finite automata.

30.05.2018

G.Evstropov "The k-sum metric combinatorial optimization problem"

Consider we have some set A and non-negative cost function w(e) of its elements, some subsets of set A are considered to be feasible. For example, A can be a set of arcs of directed graph and we are interested in simple paths from s to t. Well-known problems ask to find a subset of minimum total cost (minsum path can be solved with Dijkstra's algorithm) or a path of minimax length (bottleneck problem). K-sum optimization generalizes these two by asking to find a feasible subset that minimizes the sum of k most expensive elements. In case some subset consists of less than k elements we set its cost in k-sum metric equal to their sum.

It turns out if an O(P(n)) time algorithm exists to find minisum subset, k-sum optimum can be found in O(P(n) * n) time. In case there will be enough time we may consider the same approach for k-sum approximation and some continuous problems (such as k-sum mincost flow).

23.05.2018

G. Posobin "Random noise increases Kolmogorov complexity"

Consider a binary string x of length n whose Kolmogorov complexity equals \alpha n for some \alpha<1. We want to increase the complexity of x by changing a small fraction of bits in x This is always possible: Buhrman, Fortnow, Newman and Vereshchagin showed that the increase can be at least \delta n for large n (where \delta is some positive number that depends on \alpha and the allowed fraction of changed bits).

We consider a related question: what happens with the complexity of x when we randomly change a small fraction of the bits (changing each bit independently with some probability p)? It turns out that a linear increase in complexity happens with high probability, but the guaranteed increase is smaller than in the case of arbitrary change. We note that the amount of the increase depends on x (strings of the same complexity could behave differently), and give an exact lower and upper bounds for this increase (with o(n) precision).

The proof uses the combinatorial technique that goes back to Ahlswede, Gacs and Korner (1977).

16.05.2018

A. Romashchenko "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts"

We propose necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity.

Using this technique we provide examples of effective and non-sofic shifts on ZZ^2 with very low block complexity: the number of admissible patterns of size NxN grows only as a polynomial in N.

11.04.2018

V. Grinberg "Sum-of-squares polynomial optimization approach"

04.04.2018

Y. Nesterov "Implementable Tensor Methods in Unconstrained Convex Optimization"

In this talk we discuss new tensor methods for unconstrained convex optimization which are solving the auxiliary problems of minimizing convex multivariate polynomials. We analyze the simplest scheme, based on minimization of a regularized local model of the objective function, and its accelerated version obtained in the framework of estimating sequences. Their rates of convergence are compared with the worst-case lower complexity bounds for corresponding problem classes. Finally, for the third-order methods, we suggest an efficient technique for solving the auxiliary problem, which is based on the recently developed relative smoothness condition. With this elaboration, the third-order methods become implementable and very fast. At the same time, in many important cases the computational cost of iterations in these methods remains on the level typical for the second-order schemes.

21.03.2018

A. Milovanov "Derandomization of PIT and generalizations of the Sylvester-Gallai theorem"

in Russian

07.03.2018

A. Rubtsov "Exile of Kolmogorov Complexity from KC-DCF-Lemma"

We present a new structural lemma for deterministic context free languages. The lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by M. Li and P. Vitányi in 1995 and corrected by O. Glier in 2003. We show that in the case of proving that a language is not a DCFL (the main application of lemmata) the lemmata are equivalent. The structural lemma is much easier to apply than KC-DCF-Lemma. It also provides a new insight to the nature of DCFL. It allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.

14.02.2018

V. Grinberg "L0 Sampling and Graph Sketches"

in Russian

07.02.2018

V. Podolskii "A game approach to the sensitivity conjecture"

The famous sensitivity conjecture has many reformulations.

One of them states that the decision tree complexity of any Boolean function is polynomially related the sensitivity of this function. In this talk we will discuss a recently introduced communication game that can help to prove the sensitivity conjecture. The talk is based on the paper “A New Approach to the Sensitivity Conjecture” by Justin Gilmer, Michal Koucký and Michael E. Saks (ITCS 2015).

31.01.2018

L. Sysoeva "Some properties of the automatic closure of Boolean functions sets"

in Russian

24.01.2018

E. Mineeva "Parameterized computational complexity"

in Russian

13.12.2017

Michael Raskin "Complementing unambiguous finite automata (a superpolynomial lower bound for 1-letter alphabet)"

Two main approaches to finite automata are deterministic finite automata and nondeterministic finite automata. Deterministic finite automata can be easily combined to recognize the union, intersection or the complement of the languages recognized by original DFAs; but they might require many more states than nondeterministic finite automata.

Unambiguous finite automata are NFAs that have at most one accepting run for every word. They can be exponentially more succinct than DFAs in some cases, and there was a conjecture that recongnizing the complement of the language of an UFA can be done by another UFA with a polynomial increase in the state count (the best lower bound was quadratic).

In the talk, a superpolynomial lower bound for complementing a UFA over the one-letter alphabet will be presented.

22.11.2017

Guilhem Gamard "Quasiperiodicity on one and two-dimensional words. Continuation of previous talk: two-dimensional aspects"

We work on one-dimensional and two-dimensional words, i.e. colorings of ℤ and ℤ² with colors choosen among a finite alphabet. These objects are fundamental in several branches of computer science, thus a large amount of research is devoted to understanding how “symmetric” a word can be: for example we have the notions of periodicity, topological entropy, minimality, unique ergodicity…

Here we focus on quasiperiodicity: a finite pattern q is a quasiperiod of a word w iff w is covered with translated copies of q, which may overlap. We would like to understand the structure of q-quasiperiodic words only through properties of q. One motivation for this comes the study of quasicrystals in physics, where a 2-dimensional word represents a regular molecular structure and a quasiperiod is a configuration with local minimal energy.

08.11.2017

A. Shen "What is geometric construction and how to prove its impossibility"

in Russian

01.11.2017

Guilhem Gamard "Quasiperiodicity on one and two-dimensional words"

We work on one-dimensional and two-dimensional words, i.e. colorings of ℤ and ℤ² with colors choosen among a finite alphabet. These objects are fundamental in several branches of computer science, thus a large amount of research is devoted to understanding how “symmetric” a word can be: for example we have the notions of periodicity, topological entropy, minimality, unique ergodicity…

Here we focus on quasiperiodicity: a finite pattern q is a quasiperiod of a word w iff w is covered with translated copies of q, which may overlap. We would like to understand the structure of q-quasiperiodic words only through properties of q. One motivation for this comes the study of quasicrystals in physics, where a 2-dimensional word represents a regular molecular structure and a quasiperiod is a configuration with local minimal energy.

18.10.2017

V. Chernyshev "Dynamics of points on metric graphs"

in Russian

11.10.2017

Y. Makarychev «Algorithmic and Hardness Results for the Hub Labeling Problem»

There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of Ω(log n) for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously.

Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an O(log D) approximation algorithm for graphs of diameter D with unique shortest paths. In particular, we get an O(log log n) approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an O(log n) approximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2.

The talk is based on a joint paper with Haris Angelidakis and Vsevolod Oparin.

October 10, 2017

K. Makarychev "Clustering Billions of Reads for DNA Data Storage"

I will tell the audience how to quickly cluster billions of strings based on their similarity (edit distance). We will discuss what makes the problem hard and then explore known (theoretical/mathematical) techniques like Locality Sensitive Hashing (LSH), metric embeddings, and sketching that can be employed for clustering Big Data. Finally, I will show how we use these techniques along with some new ingredients to cluster billions of DNA strands.

I will also briefly mention how string clustering is used in the Microsoft DNA Storage project – the project that develops technology for storing data on synthesized DNA strands (https://www.microsoft.com/en-us/research/project/dna-storage/).

The talk is based on my joint work with a team of researchers from Microsoft Research and University of Washington (https://www.microsoft.com/en-us/research/project/dna-storage/). This paper will appear at NIPS 2017.

May 31, 2017

T. Iskhakov «A brief introduction to the flow algorithms»

in Russian

May 24, 2017

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

in Russian

May 10, 2017

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

in Russian

April 4, 2017

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

in Russian

April 12-19, 2017

M. Kaledin «Applications of Gröbner basis for integer programming»

in Russian

15-22.03.2017

M. Vyalyi «Fine-grained reductions»

in Russian

09.03.2017

A. Knop «Time hierarchy theorems for heuristic computations»

in Russian

22.02-03.03.2017

G. Evstropov «Optimal algorithms for solving some zero-sum games with ordered sets of coins»

in Russian

15.02.2017

D. Kutenin «A polynomial algorithm for primality testing»

in Russian

25.01.– 01.02.2017

M. Vyalyi «A quasipolynomial algorithm for solving parity games»

in Russian

11.01.2017

Tomislav Petrović "A step towards finding an infinite string which is neither random nor predictable"

We'll discuss how to convert a sequential program that uses small amount of space and large amount of time into a parallel program that uses large amount of space and small amount of time, and vice-versa.

We'll also look at a simple extension of this result to sequential programs that don't necessarily use a small amount of space, but for which we know that they visit some small set of states.

07.12.2016

K. Makarychev «Solving Optimization Problems with Diseconomies of Scale»

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as x q, with the amount x of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is A q, where A q is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for several optimization problems with a diseconomy of scale such asMinimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. In the Minimum Energy Efficient Routing problem, the goal is to route an unsplittable multicommodity flow in a network/graph between terminals so as to minimize the energy consumption on the links/edges. Our analysis relies on a decoupling inequality for nonnegative random variables. Consider arbitrary nonnegative jointly distributed random variables Y 1,…,Y n . Let X 1,…,X n be independent copies of Y 1,…,Y n such that all X i are independent and each X i has the same distribution as Y i . Then, E(X 1 +…+X n ) q < C q E(Y 1 +…+Y n ) q . The inequality was proved by de la Pena in 1990. However, the optimal constant C q was not known. We show that the optimal constant is C q =A q . This is a joint work with Maxim Sviridenko, Yahoo Labs.

09-16.12.2016

A. Shen «On normal sequences»

in Russian

02.11.2016

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

in Russian

19.10.2016

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

23.09 – 12.10.2016

G. Posobin, V. Podolskii, A. Milovanov, M. Vyalyi «Basic concepts of the Fourier analysis of Boolean functions»

in Russian

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.