В докладе будет рассказано о новой оценке на сложность D(f) вычисления булевых функций в модели разрешающих деревьев с XOR запросами . В этой модели требуется вычислить известную булеву функцию f на неизвестном входе. За один запрос разрешается узнать XOR любого подмножества входных битов. Мерой сложности является число запросов в худшем случае.

Гранулярностью gran(f) булевой функции f называется минимальное натуральное k, такое что всякий коэффициент Фурье функции f выражается как целое число, умноженное на 1/2^k. Мы докажем, что D(f) ≥ gran(f)+1. Эта нижняя оценка является усилением оценок на D(f) через l_0-норму спектра Фурье f и через степень f как многочлена над GF(2). Используя новую оценку мы находим точное значение D(f) для некоторых важных функций f, включая функцию голосования и итерированную функцию голосования. Для функции голосования сложность оказывается равной n-B(n)+1, где B(n) равно числу единиц в двоичной записи n. Для итерированной функции голосования сложность равна (n+1)/2. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.

A sequence is k-automatic if its elements are obtained when the base-k representations of integers are successively fed into a given finite automaton. For example, the famous Thue-Morse sequence abbabaabbaab... is 2-automatic: symbol a occurs at position n (indexing from 0) if and only if the base-2 representation of n contains an even number of 1's (this is checkable by a simple automaton). These k-automatic sequences are a well-studied object in combinatorics on words, and they have many good properties. One important feature is that any property of a k-automatic word that is expressible in a certain first-order logic is decidable. Moreover, these sequences satisfy many closure properties. For instance, taking the symbols whose indices are in an arithmetic progression in a k-automatic sequence is again k-automatic.

Using a more exotic way of representing integers than the usual base-k representation, this notion of a k-automatic word can be generalized. In the talk, I will introduce some unusual numeration systems, like Pisot numeration systems and Parry numeration systems. I will compare the corresponding automatic sequences with k-automatic sequences, and sketch ideas that show that the Pisot case is similar to the k-automatic case while the more general Parry-automatic sequences break many of the good properties (like decidability and closure properties mentioned above) of k-automatic sequences.

I will give definitions of automatic sequences and numeration systems, so no prior knowledge of them is needed.

Measure-Once Quantum Automata, also known as Moore-Crutchfield QFA, are the most straightforward quantum variants of probabilistic finite automata: They are obtained by replacing the stochastic matrices by unitary ones, and L1-norm by L2-norm. It turns out that the expressive power of MO-QFA is weaker than that of PFA, but sometimes the MO-QFA may be exponentially more compact than their classical counterparts.

It may appear surprising that determining the emptiness of a strict cut-point languages for MO-QFA is decidable, whereas the same question for PFA is undecidable. On the other hand, removing the attribute "strict" yields an undecidable problem for MO-QFA again. In this talk, I will demonstrate that the ambiguity problem of the acceptance probability for MO-QFA is undecidable, if some radical irrational amplitudes are allowed. It turns out that, conditional to Bombieri-Lang conjecture (or to a speculation by Don Zagier), the problem remains undecidable even if only rational amplitudes are allowed.