Колмогоровский семинар по сложности вычислений и сложности определений (Kolmogorov seminar on complexity of computations and descriptions)

Руководители:

Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09h

Будущие доклады

Date: April 22, 2024. Time: 18:30 (MSK), 17:30 (CEST)

Speaker: Ibragim Mamilov

Title: Circuits for Majority — generalizing the Valiant’s construction

Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

Прошедшие доклады

• Date: April 15, 2024. Time: 18:30 (MSK), 17:30 (CEST)

  Speaker: Thomas Steifer
  

  Title: Simple online learning with consistent oracle

  We consider online learning in the model where a learning algorithm can access the class only via the \emph{consistent oracle} — an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al.~(COLT’23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem.
  Assos et al.~gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C>0. Our estimates show that their C is of order 2^{300,000}. We give a novel algorithm that makes at most O(256^d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3^d mistakes. See https://arxiv.org/abs/2308.08055

• Date: April 8, 2024. Time: 18:30 (MSK), 17:30 (CEST)

  Speaker: Timur Kuptsov
  

  Title: Half-duplex complexity with honest adversary

  In the classical model of communication complexity we consider a cooperative game between two players, Alice and Bob, who want to compute f (x, y) for a given function f. Alice knows only x and Bob knows only y. To this end, Alice and Bob can communicate sending to each other messages, one bit per round. An important property of this communication model is the following: in each round one player sends a bit message while the other player receives it.

  Later this model was generalized in to a model describing communication over the so called half-duplex channel. A well-known example of half-duplex communication is talking via walkie-talkie: one has to hold a “push-to-talk” button to speak to another person, and one has to release it to listen. We consider a communication model where players are allowed to speak simultaneously. If two persons try to speak simultaneously then they do not hear each other and both messages are lost. If both players receive, then rounds players receive the same bits chosen by an adversary.

• Date: April 1, 2024. Time: 18:30 (MSK), 17:30 (CEST)

  Speaker: Andrei Rodin
  

  Title: Euclid’s Elements

  Everyone knows that Euclid’s Elements was the textbook that was used for
  a maximally long period. However, there are few people now who tried to
  read this book and find out what is there and how one should understand
  it. (There are more or less literal translation — Russian translation
  by Мордухай-Болтовской and several English translation, including one by
  Fitzpatrik).

  Andrei Rodin, an historian of mathematics, kindly agreed to tell us more
  about the contents (and history) of EE, answer our questions. It is
  worth trying in advance to start reading this book (in the role of
  student who really wants to pass the exam on Euclid and therefore needs
  to understand the actual and acceptable arguments, from the Euclid’s
  viewpoint]

  An appetizer: consider an ordered archimedian abelian group; we say that
  $a:b=c:d$ for four positive elements $a,b,c,d$, if $ma>nb$ implies
  $mc>nd$, $ma=nb$ implies $mc=nd$, and $ma<nb$ implies $mc<md$. Can you
  prove that $a:b = c:d$ implies $a:c = b:d$? (Book VI, proposition 16)

• Date: March 11, 2024. Time: 18:30 (MSK), 16:30 (CET)

  Speaker: Nikolay Vereshchagin
  

  Title: Vapnik — Chervonenkis theorem

  The Vapnik — Chervonenkis theorem states that the observed quality of any inferred hypothesis (in the course of learning) is close to its real quality assuming that the class H of used hypotheses has small VC-dimension. Some time ago A. Shen told us the proof of this theorem in the case when the learned function belongs to H. This time I will prove the theorem in the general case.

• Date: March 04, 2024. Time: 18:30 (MSK), 16:30 (CET)

  Speaker: Alexander Shen

  Title: Combinatorial rectangles, Kolmogorov complexity and experts’ aggregation

  There is a classical result in communication complexity saying that if some communication protocol is applied to jointly distributed inputs a and b, then the transcript \pi has a non-negative «triple information with a and b». We will discuss its meaning, extension to partitions, Kolmogorov complexity version for one rectangle, implication for a combinatorial game and interpretation of this game in terms of aggregation experts’ opinions.

• Date: Dec. 4, 2023. Time: 18:30 (MSK), 16:30 (CET)

  Speaker: Alexander Shen

  Title: Rectangles, complexity and games (based on discussions with A.Kozachinsky and A.Romashchenko)

  There are several cases that allow translation between probabilisitic,
  combinatorial and complexity ststements. We look at some inequalities
  (form papers of Romashchenko, Kaced, Zimand, Vereshchagin), extend them
  for multidimensional case and observe that they have a natural game
  interpretation. So the question (open) is to find a direct combinatorial
  proof for the corresponding combinatorial statements. (It could be
  interesting since the complexity proof uses some tricks more than once.)

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• November 27, 2023. Time: 18:30 (Moscow time).

  Speaker: Nikolay Vereshchagin

  Title: Improving Solovay’s theorem. Part II.

  Let CE(S) denote the length of the shortest program enumerating a (computably enumerable) set S. Let AE(S) stand for the probability that the universal randomised Turing machine enumerates S. It is easy to show that if AE(S) is positive then S is a c.e. set. Solovay proved a quantitative version of this statement: if AE(S)>1/2^k then CE(S)<3k. Recently Shekhovtsov and Zakharov improved Solovay’s theorem by replacing the constant 3 by the constant 2 in this inequality. It remains unknown whether we can further reduce this constant.

  In the talk, the proof of Shekhovtsov — Zakharov’s theorem will be presented.

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• November 20, 2023. Time: 18:30 (Moscow time).

  Speaker: Nikolay Vereshchagin

  Title: Improving Solovay’s theorem. Part I.

  Let CE(S) denote the length of the shortest program enumerating a (computably enumerable) set S. Let AE(S) stand for the probability that the universal randomised Turing machine enumerates S. It is easy to show that if AE(S) is positive then S is a c.e. set. Solovay proved a quantitative version of this statement: if AE(S)>1/2^k then CE(S)<3k. Recently Shekhovtsov and Zakharov improved Solovay’s theorem by replacing the constant 3 by the constant 2 in this inequality. It remains unknown whether we can further reduce this constant.

  In the talk, the proof of Shekhovtsov — Zakharov’s theorem will be presented.

• Speaker: Ivan Baburin

  Title: Algebraic Matching Algorithms

  In this presentation we will explore algebraic algorithms for computing perfect matchings in bipartite and general graphs. These algorithms are of great importance for the complexity theory, since they can be easily parallelized, which is not true for “classical” matching algorithms such as Edmond-Blossom. In the talk we present the following two algorithms:
  1. The randomised algebraic algorithm for verifying the existence of a perfect matching in bipartite and non-bipartite graphs. The algorithm for bipartite graphs verifies whether the determinant of the adjacency matrix is non-zero, and the general algorithm uses a similar approach for Tutte’s matrices. The existence algorithm can be modified to find a perfect matching, as a consequence we have that finding perfect matchings is in RNC.2. Derandomized version of the algorithm for verifying the existence of bipartite perfect matchings running in quasi-polynomial time. Similarly it can be modified to find perfect matchings, which puts the bipartite matching problem in quasi-NC.

  Zoom link: https://us06web.zoom.us/j/82818031821?pwd=VjBMWUtvWHJmc3hybGNNWmg5QTFKQT09

• October 23, 2023. Time: 18:30 (Moscow time).

  Speaker: Alexander Kozachinsky

  Title: Lempel-Ziv algorithm revisited. Part II

  It is «well known» that Lempel-Ziv compressing algorithm is asymptotically not worse than block coding for blocks of arbitrary length (and does not require knowing the block size or frequencies in advance). However, the original papers of Lempel and Ziv are hard to read, so a clean proof could be useful. It can be obtained by combining finite-state compression for block codes and superadditivity for finite-state complexity.

• October 16, 2023. Time: 18:30 (Moscow time).

  Speaker: Alexander Kozachinsky

  Title: Lempel-Ziv algorithm revisited. Part I

  It is «well known» that Lempel-Ziv compressing algorithm is asymptotically not worse than block coding for blocks of arbitrary length (and does not require knowing the block size or frequencies in advance). However, the original papers of Lempel and Ziv are hard to read, so a clean proof could be useful. It can be obtained by combining finite-state compression for block codes and superadditivity for finite-state complexity.

  Zoom link: https://us06web.zoom.us/j/82818031821?pwd=VjBMWUtvWHJmc3hybGNNWmg5QTFKQT09

• October 9, 2023. Time: 18:30 (Moscow time).

  Speaker: Rustam Zyavgarov (Рустам Зявгаров)

  Title: Extraction of the mutual information (Выделение общей информации)

  [in English] It is known that the mutual information between a line X and a point Y lying on it (on a discrete plane) is non-materializable. This means that any word Z that has low complexity both relative to X and relative to Y must have low unconditional complexity. This statement can be refined and written as an inequality connecting the conditional complexities KS(Z|X) and KS(Z|Y) and the unconditional complexity KS(Z). We will generalize this result by proving the non-materializability of general information for pairs XU and YV obtained from a line and a point by assigning random words to U and V. To prove this result, we use two methods: the inclusion-exclusion method proposed by Muchnik, as well as the spectral method (expander mixing lemma).

  [in Russian] Известно, что общая информация пары из прямой X и лежащей на ней точки Y (на дискретной плоскости) нематериализуема. Это значит, что всякое слово Z, имеющее малую сложность одновременно относительно X и относительно Y, должно и само иметь малую безусловную сложность. Это утверждение можно уточнить и записать в виде неравенства, связывающего условные сложности KS(Z|X) и KS(Z|Y) и безусловную сложность KS(Z). Мы обобщим этот результат, доказав нематериализуемость общей информации для пар XU и YV, полученных из прямой и точки приписыванием случайных слов U и V. Для этого мы используем два метода: метод включений-исключений, предложенный Мучником, а также спектральный метод (экспандерную лемму о перемешивании).

  Zoom link: https://us06web.zoom.us/j/82818031821?pwd=VjBMWUtvWHJmc3hybGNNWmg5QTFKQT09

• May 15 and May 22, 2023. Time: 17:00 (Moscow time)

  Speaker: Maxim Babenko and Ruslan Savchenko

  Title: Yandex’ file system

  Maxim Babenko and Ruslan Savchenko will speak about their experience as designers and developers of infrastructure used at Yandex (Map-Reduce type) and about an open source project they created.

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• April 17, 2023. Time: 17:00 (Moscow time)

  Speaker: Alexander Kozachinskiy

  Title: Deciding approximately satisfiable k-CNF

  I will talk about the following result of Akmal and Williams (FOCS 2021): for any positive integer k and for any rational number rho from (0, 1) there exists a polynomial-time algorithm that, given a k-CNF C over n variables, decides whether at least rho * 2^n inputs to C satisfy it. I hope to present the proof for k = 3.

• April 10, 2023. Time: 17:00 (Moscow time)

  Speaker: Alexey Slizkov (HSE)

  Title: Computational bounds for the 2048 game

  2048 is a single player video game, played by millions mostly on mobile
  devices. We prove rigorously for the first time that there is an
  algorithm with winning probability at least 0.99969, and that there is a
  strategy for achieving the 256 tile guaranteed (with probability 1).

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• March 27, 2023. Time: 17:00 (Moscow time)

  Speaker: Alexander Kozachinskiy

  Title: Computational PAC learning

  We will continue discussing computational PAC learning. Alexander Kozachinskiy will present two learning algorithms, one for decision trees, and the other for DNFs.

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• March 20, 2023. Time: 17:00 (Moscow time)

  Speaker: Bruno Bauwens (and maybe Sasha Kozachinskiy)

  Title: PAC learning (continued)

• March 13, 2023. Time: 18:30 (Moscow time)

  Speaker: Bruno Bauwens

  Title: PAC learning (continued)

• March 6, 2023. Time: 18:30 (Moscow time)

  Speaker: Bruno Bauwens

  Title: PAC learning

  We prove 3 basic results of polynomial time PAC-learnability as defined in [1]. We study proper and improper learning in the realizable setting. Proofs in our example cover AdaBoost and SVM, two algorithms that are thought in most machine learning courses.— Half spaces are PAC-learnable. We using hard-margin SVM and leave-one-out risk, thus without VC-dimensions.— If P != NP, then 2-term DNF’s are not properly PAC learnable. But 2-term DNF’s are improperly PAC learnable.

  — Weak PAC learnability is equivalent to PAC learnability (using AdaBoost).

  If time permits, we overview recent results regarding agnostic PAC-learnability of halfspaces.

  [1] Valiant, A theory of the learnable, 1984, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=b8f0f258827a1bdc1c0828c9fb7a913a6bcc3d2d
  [2] Kearns and Vazirani, An introduction to computable learning theory, 1994.
  [3] Mohri, Rostamizadeh, and Talwalkar, Foundations of Machine Learning, 2018, https://cs.nyu.edu/~mohri/mlbook/

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• February 20, 2023. Time: 18:30 (Moscow time)

  The continuation of Tomasz Steifer’s talk on Computable PAC learning.

  Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• February 13, 2023. Time: 19:30 (Moscow time)

  Speaker: Tomasz Steifer (Pontifical Catholic University of Chile)

  Title: Computable PAC learning

  The fundamental problem in the theory of Machine Learning is to understand when a given hypothesis class can be learned by an algorithm that has access to finitely many random samples of an unknown objective function. The goal of the learner is to select a function that approximates the objective function at least as well as any hypothesis from the given class. The fundamental theorem of statistical learning provides a characterization of the existence of learners for a given hypothesis class in terms of the finitude of a combinatorial quantity (VC dimension) associated to the class (Vapnik and Chervonenkis, 1971; Blumer et al., 1989). This characterization is concerned with the existence of learners as abstract mathematical functions, and does not take into account its computational properties.Recently, a new framework combining PAC learning and Computability Theory was proposed by Agarwal et al. (2020). In computable PAC (CPAC) learning, both the learner and the functions it outputs are required to be computable, in the sense that they can be computed by a Turing Machine. As observed in Agarwal et al. (2020), the existence of a computable learner no longer follows from finite VC dimension. Moreover, the computable setting is sensible to aspects of the problem that make no difference in the classical setting. For example, it becomes important whether the learner is required to be proper (i.e, constrained to only output functions that belong to the hypothesis class) or allowed to be improper (can output arbitrary functions). Another issue is whether the sample
  complexity, i.e., the number of samples a learner needs in order to work as requested, can always be bounded by a computable function (a setting referred to as strong CPAC learning). This rises a number of natural questions — which of these aspects of the problem actually lead to different versions of computable learnability? In the talk, we will survey what is known in this area.

  Zoom link for this talk: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• December 12, 2022. Time: 17:00 (Moscow time)

  Speaker: Andrés Abeliuk

  Title: Application of game theory to computational social science

  Some of the results of the talk are from this paper:
  https://www.pnas.org/doi/10.1073/pnas.2018340118

  Zoom link for this talk: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• December 5, 2022. Time: 17:00 (Moscow time)

  Speaker: Nikolay Vereshchagin

  Title: Simultaneous minimization of complexities

  The initial question: consider three strings x,y,z. Then the minimal program p that gets x from z has length C(x|z) by definition, and the minimal program qthat gets y from z has length C(y|z). Is it possible to find a pair (p,q) of programs with
  these properties (of the minimal or approximately minimal lengths mapping z to x|y) such that _complexity_ of the pair (p,q) is close to the minimal possible (i.e., to C(x,y|z))? The answer is (somewhat surprisingly) negative, and the proof of this result and some related ones will be explained.

  Zoom link for this talk: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• 28 november 2022, 17:00 (Moscow time)

  Speaker: Alexander Shen

  Title: Kraft-Barmpalias [again] and Gacs-Kucera

  Using some remark of Bauwens, one could make the proof of Kraft-Barmpalias lemma even simpler than I tried to present last time
  — we will go again over it, and also show how this can be applied to prove Gacs-Kucera theorem (every sequence is computable with some random oracle). (There is still some open question about an improved bound for oracle use)

  Zoom link for this talk: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• Speaker:Pierre Ohlmann (University of Warsaw)

  Title:Infinite duration games, memory, and graphs

  Time: 17:00 Moscow time, Oct. 31 and Nov. 7 2022

  In this talk, I will give a broad overview of the field of infinite duration games: why do we care about them, and what are the main open questions. I will then discuss a new approach to making progress on these questions by reducing them to problems about (directed) graphs.

  Zoom link for these talks: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

• Speakers: Laurent Bienvenu, Mikhail Raskin, Alexander Shen

  Title: Kraft, Chaitin and Barmpalias revisited

  Time: 17:00 Moscow time, 24 october 2022

  Abstract. Kraft-Chaitin lemma provides a memory allocation algorithm: it gets a sequence of integers l_1, l_2,… such that \sum 2^{-l_i} <=1, and returns (in an online fashion) a sequence of incomparable strings x_1,x_2,… of the corresponding lengths.
  George Barmpalias generalized this construction and proved and hierarchical version of this lemma: now the request l_i can be not only
  of the form «give me some new space», but also of the form «give me some space inside the space allocated for earlier request». This is useful
  when we want to construct, for some sequence \alpha, its compressed version \beta when the prefixes of \beta can be decoded to prefixes of
  \alpha. There are also some results about possible limits of that type of compression.

• 3 и 10 октября 2022 года.

  Доклад Н.К. Верещагина (на англ. языке)

  «Алгоритмические проблемы как игры.»

  Аннотация.
  Каждую алгоритмическую проблему можно понимать как игру с полной информацией двух игроков. Разрешимость проблемы означает существование алгоритма, вычисляющего выигрышную стратегию в этой игре. Сводимость одной проблемы к другой также можно понимать как игру того же типа. Такой подход к теории алгоритмов был развит в работах Бласса и Джапаридзе и является интересной альтернативой подходу Медведева, согласно которому алгоритмическая проблема задается семейством всюду определенных функций, а ее решением является алгоритм вычисления некоторой функции из семейства.

• 19 сентября 2022 года.
  Продолжение доклада Лорана Бьенвеню (на англ. языке)

• 12 сентября 2022 года.
  Доклад Лорана Бьенвеню на тему

  «Вероятностные предсказательные стратегии.» (на английском языке)
  Аннотация.
  Будет исследован вопрос, насколько меняется класс непредсказуемых последовательностей при разрешении предсказывающей стратегии использовать случайность.

• 23 мая 2022 года.
  Доклад М. Андреева и М. Дектярева на тему

  « Логарифмический разрыв между полудуплексной коммуникационной сложностью с противником и обычной коммуникационной сложностью для некоторой частичной функции.«
  Аннотация.
  Будут рассказаны два доказательства гипотезы, сформулированной в докладе Н. Верещагина. Гипотеза утверждает наличие логарифмического разрыва между полудуплексной коммуникационной сложностью с противником и обычной коммуникационной сложностью для некоторой частичной функции.

• 18 и 25 апреля 2022 года.
  Доклад А.В. Смаля на тему

  « Super-cubic lower bound for generalized Karchmer-Wigderson games «
  Аннотация.
  We prove a super-cubic lower bound on the size of a communication
  protocol for generalized Karchmer-Wigderson game for some explicit
  function f:{0,1}^n -> {0,1}^{log n} . Lower bounds for original
  Karchmer-Wigderson games correspond to De Morgan formula lower bounds,
  thus the best known size lower bound is cubic. The generalized
  Karchmer-Wigderson games are very similar to the original ones, so we
  hope that our approach can provide an insight for proving better lower
  bounds on the original Karchmer-Wigderson games, and hence for proving
  new lower bounds on De Morgan formula size.To achieve super-cubic lower bound we adapt several techniques used in
  formula complexity to communication protocols, prove communication
  complexity lower bound for a composition of several functions with a
  multiplexer relation, and use a technique from our previous work to
  extract the «hardest» function from it. As a result, in this setting
  we are able to show that there is a relatively small set of functions
  such that at least one of them does not have a small protocol. The
  resulting lower bound of Omega(n^{3.156}) is significantly better than
  the bound obtained from the counting argument.В первый раз будут рассказаны основные идеи и высокоуровневое описание доказательств, а во второй раз детали.

• 4 и 11 апреля 2022 года.
  Доклад Н.К. Верещагина на тему

  « Полудуплексная коммуникационная сложность с противником «
  Аннотация. Полудуплексная сложность матрицы определена так: Алиса и Боб беседуют по рации, в каждый такт общения каждый партнер в зависимости от своего входа и истории общения, либо нажимает кнопку RECEIVE, либо кнопку TALK и тогда посылает один бит. Если оба нажимают кнопку TALK, то они не слышат друг друга, но не знают об этом. Eсли оба принимают, то они слышат то, что посылает им противник (это могут быть разные биты). Входом Алисы является номер строки, а входом Боба — номер столбца. Цель — узнать соответствующий элемент матрицы. Будет приведен пример матрицы, у которой полудуплексная сложность меньше классической коммуникационной сложности.

• 21 марта 2022 года.
  Доклад Максима Ушакова на тему

  « Как работают и что умеют большие языковые модели «
  Аннотация. В дополнение к докладу Николая Григорьева Максим Ушаков расскажет о
  своём опыте использования обучающихся систем работы с текстами и про их
  возможности на практике (чего можно добиться, что для этого надо делать
  и т.п.) — и попробует что-нибудь показать.=====ввод:Бетховен написал девять симфоний, из которых наиболее известны,
  пожалуй,
  пятая и девятая. Последняя часть девятой симфонии — хор, который
  теперь сталRuGPT3:…Симфония была написана в 1809 году, правда сразу же после смерти
  Бетховена. Она предназначалась для оркестра, который состоял из 10
  инструментов (4 кларнета, 3 гобоя, 2 фагота, 2 валторны, 2 трубы, 2
  кларнеты и арфа). Первая часть «Larghetto» была опубликована в виде
  фортепианного соло, а во втором произведении симфония уже исполняется в
  оркестровом варианте.В какой-то степени это произведение очень похоже на произведение 19-го
  века «Арагонская хота».
  В симфониях Бетховен использовал несколько нетрадиционные для того
  времени оркестровые средства. В частности, для построения частей часто
  витают мелодии из всех симфониц, а оркестранты принимают знаки
  дирижера.
  Дирижер же управляет игрой инструментов по содержанию.
  Вот насколько интересно было композитору сочинять свою первую симфонию!
  А еще, есть версия, что именно под влиянием этой симфоники Сталиным
  была
  написана Симфония номер один. Я уже не помню, по какому поводу была
  написана эта симфоничность, но помню, что очень волновалась и
  специально
  ходила на прослушивание.
  Но вот то, что Бетховену удалось создать на удивление цельное творение,
  это факт!

• 14 и 28 марта 2022 года.
  Доклад А.Е. Ромащенко на тему

  « Кластеры для информационного расстояния «
  Аннотация.
  В известной статье Bennett—Gacs—Li—Vitanyi—Zurek (1998) было введено понятие алгоритмического информационного расстояния. Данное расстояние между двумя словами определяется как длина кратчайшей программы, которая переводит заданные объекты друг в друга. Красивый результат, доказанный Bennett et al., утверждает, что длина такой программы (одной программы, выполняющей перевод двух объектов друг к другу в обоих направлениях) примерно равняется максимуму длин двух кратчайших программ, осуществляющих преобразование одного из слов в другое в одном из направлений (т.е., максимум из двух условных колмогоровских сложностей).Назовем кластером множество слов с достаточно малыми попарными информационными расстояниями. Мы покажем, что в любом плотном кластере (т.е., в кластере, число элементов в котором достаточно велико, а попарные информационные расстояния достаточно малы) можно выделить ядро — такое слово, сложность которого равна взаимной информации для большинства пар слов в кластере, и которое при этом имеет очень малую сложность относительно любого элемента кластера. Иначе говоря, ядро представляет собой материализацию общей информации всех элементов кластера.Метод выделения ядра кластера используется в частности для доказательства материализации взаимной информации для троек слов.https://arxiv.org/abs/2110.01346

• 14 февраля 2022 года.
  Доклад Николая Григорьева (Deep Mind) на тему

  « Как работают и что умеют большие языковые модели«
  Аннотация.
  Языковые модели — механизм вероятностного моделирования языка. В
  последние 3-4 года происходит взрывное развитие моделей на базе deep
  learning: они становятся все больше и достигают немыслимых ранее
  результатов в порождении текста. Я расскажу немного про их историю,
  внутреннее устройство и про то, что они умеют, а потом попробую
  предположить, куда все это будет развиваться.- Что такое языковая модель
  — Зачем они нужны
  — Метрики и бенчмарки
  — Предыстория: HMM-модели
  — Ранние модели на нейронных сетях
  — Начало взрыва: Transformer. Механизм внимания (attention)
  — Важные модели: ELMO, BERT, GPT-2, Transformer-XL
  — Современные большие модели: GPT-3, Gopher, Megatron-Turing
  — Чего можно ждать дальше.

• 6 декабря 2021 года.
  Cheuk Ting Li

  « On the Undecidability of Conditional Affine Information Inequalities and Conditional Independence Implication with Cardinality Constraints.«

  Доклад состоится в необычное время 12:30 (MSK)

  Abstract.
  The conditional independence implication problem is to decide whether several statements on the conditional independence among several random variables implies another such statement. For examples, «X indep. of (Y,Z) implies X indep. of Y» is true, whereas «(X indep. of Y, and X indep. of Z) implies X indep. of (Y,Z)» is false. Despite being a fundamental question in probability theory, there is no known algorithm that can solve this problem. It is currently unknown whether this problem is even decidable (i.e., whether such algorithm exists). In this talk, we show that this problem is undecidable if we also allow imposing cardinality constraints (e.g. «X is a binary random variable»). We also show the undecidability of conditional information inequalities if we allow comparison against constants (i.e., affine inequalities). These are proved via a connection between conditional independence implication and the domino problem about tiling the plane with a set of tiles.

• 22 и 29 ноября 2021 года
  Доклад А. Козачинского на тему

  « Существование цены в играх Блэквелла.«
  Аннотация.
  В игры Блэквелла играют так. Происходит бесконечно много раундов. На каждом раунде двое игроков играют в конечную матричную игру. Бесконечная последовательность исходов этих матричных игр определяет исход глобальный игры.Оказывается, что у таких игр всегда существует цена в смешанных стратегиях (если функция, оценивающая исходы, борелевская). Это вывел Дональд Мартин из другой своей знаменитой теоремы о разрешимости детерминированных борелевских игр. Я расскажу, как он это сделал.

  15 ноября 2021 года
  Доклад Н. К. Верещагина на тему

  «Подстановочные замощения (substitutional tilings)«.
  Аннотация. Пусть дано конечное множество многоугольников. Подстановкой называется способ разрезания каждого из этих многоугольников на несколько многоугольников, каждый из которых подобен одному из исходных с некоторым постоянным коэффициентом подобия k. С каждой подстановкой можно естестественным образом сопоставить семейство замощений плоскости, называемых подстановочными замощениями (связанными с данной подстановкой). Будет рассказано о разных интересных подстановочных замощениях и предложен новый пример семейства подстановочных замощений.

• 8 November 2021
  The talk by Floris Persiau

  Randomness & Imprecision: some first steps and open questions
  Abstract.
  The field of algorithmic randomness studies what it means for infinite (binary) sequences to be random for some given uncertainty model. Classically, such randomness involves precise uncertainty models, and it is only recently that imprecision has been introduced into this field by also allowing for closed probability intervals. As a consequence, the investigation into how imprecision alters our view on random sequences has only just begun. In this talk, I will explain how we allow for non-precise uncertainty models and what additional mathematical
  structure is revealed by doing so. Furthermore, I will pose some new questions (e.g., what are the differences between precise and imprecise notions of randomness?) and put some old questions in a new perspective (e.g., what are the differences between Martin-Löf, computable, Schnorr and Church randomness).
  Слайды
  Видеозапись доклада

• 1 ноября 2021 года
  Доклад А.Шеня  на тему

  Теорема Кучеры — Гача: доказательство по Левину.
  Аннотация. Теорема говорит, что всякая последовательность нулей и единиц вычислима с некоторым случайным в смысле Мартин-Лёфа оракулом (существует случайная последовательность, к которой она сводится по Тьюрингу). Исходное доказательство строило сводящую машину некоторым искусственным способом, а хотелось воспользоваться тем, что образ равномерной меры при универсальном отображении — максимальная полумера, и всякая последовательность относительно неё в каком-то смысле «случайна». Биенвеню и соавторы доказали, что прямо так этот план не сработает, а Левин придумал, как его исправить и дал простое доказательство как самой теоремы Кучеры-Гача, так и её усилений. Я попробую про это (и про некоторое обобщение его результата) рассказать.

• 25 октября 2021 года
  Доклад Н. К. Верещагина на тему

  «Апериодические замощения плоскости равнобедренными прямоугольными треугольниками«.
  Аннотация. Можно ли замостить плоскость равнобедренными прямоугольными треугольниками
 двух цветов так, чтобы треугольники соседствовали только по целой стороне, 
причем в этом случае они были разного цвета (аналогично раскраске 
шахматной доски)? Несложно нарисовать такое периодическое замощение.
 Будет рассказано, как после добавления новых цветов на стороны плиток с помощью локальных правил
 их соединения определить естественное семейство таких непериодических замощений.
  Слайды

• 11 октября и 18 октября 2021 года
  Доклад А. Е. Ромащенко на тему

  «Бесконечное число нешенноновских информационных неравенств«.

  Аннотация. Для набора из k совместно распределенных случайных величин можно вычислить 2^k-1 значений энтропии Шеннона: энтропию каждой из этих величин, энтропию каждой пары, каждой тройки, и т.д. Для данных значений выполняются  «базисные» шенноновские неравенства, например,

  H(x) \le H(x,y) (монотонность энтропии,  a.k.a. неотрицательность относительной энтропии)

  H(x,y) \le H(x) + H(y)  (субаддитивность, a.k.a. неотрицательность взаимной информации),

  H(x,y,z) + H(z) \le H(x,z) + H(y,z) (субмодулярность, a.k.a. неотрицательность относительной взаимной информации).

  Известно, что никаких принципиально других линейных неравенств для энтропий пар или троек случайных величин не бывает. Однако для больших наборов величин известны также некоторые «нешенноновские» неравенства дл энтропии, не представимые в виде линейной комбинации базисных. Первое неравенство такого вида было открыто в 1998 году (Z.Zhang, R.W.Yeung).

  Мы обсудим теорему Матуша (Frantisek Matus, 2007) о том, что для четверок случайных величин имеется бесконечно много независимых информационных неравенств.

  Оригинальная статья:  Frantisek Matus. «Infinitely many information inequalities.» In 2007 IEEE International Symposium on Information Theory, pp. 41-44. IEEE, 2007.

• 4 октября 2021 года
  Доклад Н.К. Верещагина на тему
  Преобразование MA протоколов в АМ протоколы с точки зрения количества случайных битов.

  Аннотация.
  Хорошо известно, что MA включено в AM и в PP.
 Стандартное преобразование MA протокола, в котором количество случайных бит Артура равно a, а длина сообщения
Мерлина равна m, требует O(ma) случайных бит в новом протоколе.
 То же самое верно и для преобразования MA протокола в PP машину.
 В диссертации А.Кнопа был поставлен вопрос, можно ли 
O(ma) заменить на некоторый многочлен только от a.
 Аналогичный вопрос естественно поставить и для PP машин.
 Мы доказываем, что 
 относительно некоторого оракула оба преобразования требуют
 не менее m+a случайных бит. Более того, 
 это же верно и для AM протоколов, в которых вероятность ошибки не отделена от 1/2
 (PP*NP-протоколы), обобщающих как обычные AM протоколы, так 
 и PP машины.
  Слайды

• 27 сентября 2021 года

  Как нам следует оценивать атлетов и кандидатов

  Авторы: Кондратьев А.Ю., Яновский Е.А., Нестеров А.С. (все ВШЭ-СПб)

  Аннотация.
  Мы изучаем, как ранжировать кандидатов с помощью позиционных балльных правил. Каждая позиция в каждом индивидуальном ранжировании дает определенное количество очков, а общая сумма очков определяет итоговое ранжирование. Мы хотим, чтобы выполнялся принцип согласованности: когда какой-то кандидат удаляется, то итоговое ранжирование остальных кандидатов не меняется. Этот принцип важен в ситуациях, когда множество кандидатов может меняться, а итоговое ранжирование определяет последовательность действий: кого звать на интервью, если лучший претендент отказался? Кому вручать кубок, если победитель был пойман на допинге? Какой фильм рекомендовать к просмотру, если лучший фильм все уже смотрели? Изменится ли результат выборов при добавлении спойлера? К сожалению, полностью согласованных балльных правил не существует, однако, мы можем потребовать более слабую версию согласованности. Существуют балльные правила, которые остаются согласованными, если мы удаляем или добавляем единогласного победителя, например, атлета с подозрительно сильными результатами. Аналогично, мы можем удалять или добавлять единогласного проигравшего, например, спойлера на выборах. Почти ничего не ограничивающие по отдельности, вместе эти два принципа характеризуют однопараметрическое семейство с геометрическими, арифметическими и обратными геометрическими последовательностями очков. Наше семейство содержит три крайних правила: подсчет Борда, медальную систему и обратную медальную систему; мы приводим новые элегантные характеризации этих правил. Затем мы показываем как, эта постановка с одним параметром помогает выбирать подходящие балльные правила для различных приложений.

• 20 сентября 2021 года
  Обсуждение открытых вопросов в колмогоровской сложности.

  Слайды  | Запись доклада да YouTube

   

• 13 сентября 2021 года
  Доклад А. Шеня на тему
  Открытые вопросы в колмогоровской сложности.

  Запись доклада на YouTube | Записи на доске

  Аннотация.
  По предложению SIGACT, Андрей Ромащенко, Мариус Зиманд и я (Шень) пытаемся собрать некоторые давно открытые и мало изученные вопросы, относящиеся к колмогоровской сложности — их можно будет обсудить на занятии.

Страница семинара в базе данных мехмата.См. также: Научные семинары кафедры