• 14 июня 2017, среда
  • Москва, Кочновский проезд, 3

Workshop on Complexity of Computation, Communication, Descriptions and Proofs

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

Школа Прикладной Математики и Информатики МФТИ
890 дней назад
14 июня 2017, начало в 10:30
Кочновский проезд, 3

Detailed information and registration is available on the website of the workshop: cs.hse.ru/big-data/tcs-lab/cccdp/.....


Next Wednesday, June 14, the laboratory of Theoretical Computer Science will hold a Workshop "Complexity of Computation, Communication, Descriptions and Proofs" on a broad range of topics in Theoretical Computer Science. We will have five guest speakers with survey talks on their area of expertise. The workshop will be held in CS Department building, Room 205. It starts at 10:30, June 14. The language of the workshop is English. Detailed information and registration is available on the website of the workshop: https://cs.hse.ru/big-data/tcs-lab/... Please register if you are considering to come.



Amnon Ta-Shma (Tel-Aviv University)

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\eps}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an explicit $\eps$-biased set over $k$ bits with support size $O(\frac{k}{\eps^{2+o(1)}})$. This improves upon all previous explicit constructions which were in the order of $\frac{k^2}{\eps^2}$, $\frac{k}{\eps^3}$ or $\frac{k^{5/4}}{\eps^{5/2}}$. The result is close to the Gilbert-Varshamov bound which is $O(\frac{k}{\eps^2})$ and the lower bound which is $\Omega(\frac{k}{\eps^2 \logeps})$.

The main technical tool we use is bias amplification with the $s$-wide replacement product. The sum of two independent samples from an $\eps$-biased set is $\eps^2$ biased. Rozenman and Wigderson showed how to amplify the bias more economically by choosing two samples with an expander. Based on that they suggested a recursive construction that achieves sample size $O(\frac{k}{\eps^4})$. We show that amplification with a long random walk over the $s$-wide replacement product reduces the bias almost optimally.



Dmitry Sokolov (St. Petersburg Department of Steklov Institute of Mathematics)

In early 90’s Krajíček introduced a so-called “interpolation technique” for proving lower bounds on the size of propositional proof systems. The crucial idea of this technique is an “extraction” of small monotone circuit for some hard function from a small proofs.

In order to describe the essence of this technique let us consider a monotone function f : {0, 1}n → {0, 1} from the class �� that cannot be computed by small monotone circuit. Let Zero(x, r) is the “reasonable encoding” with additional variables r, the fact that x ∈ f−1(0), and let formula One(x, q) is the “reasonable encoding” with additional variables q, the fact that x ∈ f−1(1). Krajíček showed for big enough class of proof systems (resolution, LK without cut rule, etc.) that if there is a proof of size S of the unsatisfiable formula Zero(x, r)∧One(x, q), then one can create a circuit of size poly(S, n) for the function f.

By using this general idea Pudlák gave a lower bound on the size of proofs in the Cutting Planes proof system (and it is still the only known technique for proving lower bounds for the CP).

In this talk we consider the ways of “extraction” of monotone circuits, limitation of this technique and recent results in this area.


Bruno Loff (University of Porto)

We will be interested in understanding the communication complexity of a composition problem. Here we have a two-party Boolean function g(x, y), and some function f(z) on p bits, and two players Alice and Bob who wish to compute the composition f ∘ g. I.e., Alice is given x1, …, xp and Bob is given y1, …, yp, and they wish to know f(g(x1, y1),…,g(xp, yp)).

It is easy to see that the communication complexity of f ∘ g will never be more than the query complexity of f times the communication complexity of g. Both players can simulate the decision-tree for f and every time they wish to know a bit in f’s input, they communicate and solve the corresponding instance of g. We overview several new results showing that, for some choices of g, this turns out to be the optimal protocol for *any* f


Grigory Yaroslavtsev (Indiana University, Bloomington)

I will introduce a model for Massively Parallel Computation (MPC) that has recently emerged to capture aspects of computation in big data processing systems (such as MapReduce and Spark). This model emphasizes depth of the computation as a key metric of performance under certain computational and communication constraints. I will show how to solve some basic computational problems such as sorting and graph connectivity in MPC. We will also see a summary of existing results and main open questions in the area and illustrate connections to other well-studied models used to describe computational and communication complexity in data processing. This talk will be self-contained and won’t assume prior familiarity with massively-parallel computation.


Stephen Fenner (The University of South Carolina)

I will describe a cluster of recent results that help to derandomize some parallel algorithms for graphs and matroids. Specifically, it has been shown that the problem of finding a perfect matching in a graph is in the complexity class quasi-NC, that is, it is solvable in polylogarithmic time (that is, $\log^{O(1)} n$ time) time using quasipolynomially many processors (that is, $2^{\log^{O(1)} n}$ many processors). This was first shown for bipartite graphs by F, Gurjar, and Thierauf in 2015, and a proof for general graphs was recently announced by Svensson and Tarnawski (April 2017). In the interim, Gurjar and Thierauf (2016) gave a quasi-NC algorithm for the Linear Matroid Intersection problem. All these results use similar techniques that are based in geometry--for example, discovering lower dimensional faces of the perfect matching polytope of a graph. I will emphasize these geometrical techniques in the talk.



Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше