Problems in Theoretical Computer Science 2021

Marc Vinyals, St. Petersburg State University, R401

Query to communication lifting theorems form a useful set of tools that allow us to translate results from query complexity into communication complexity. One drawback from lifting is that the hardness of a function inherent to the theorem, called the gadget, carries on to the resulting problem. This can make the resulting problem larger and harder than the original in ways that we do not want. Proving a standard lifting theorem that works with a simple constant-size gadget is an open problem. In this talk we will show that we can still prove more exotic theorems that work with different measures, work with simple gadgets and are enough for some applications.

Andrey Storozhenko, UCLA, R401

We prove that for every decision tree, the sum of the absolute values of the Fourier coefficients of given order $L > 1$ is upper bounded by approximately square root of $d$ choose $L$, where $d$ is the tree depth. Our bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with $L$, becoming trivial already at $L = d$. As an application, we obtain, for every integer $k > 1$, a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $k/2$ and randomized query complexity $\Omega(n^{1−1/k})$. This separation of bounded error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation (Tal, FOCS 2020) was polynomially weaker. As another application, we obtain an essentially optimal separation for bounded-error quantum versus randomized communication complexity.

Alexander Smal, PDMI RAS, R401

Unlike the classical model of communication complexity, in the half-duplex communication model Alice and Bob can speak simultaneously, as if they were talking using a walkie-talkie. If both players speak simultaneously they don't hear messages of each other. The motivation for such a communication model comes from the study of the KRW conjecture. We study how half-duplex communication complexity is different from the classical one. The talk will cover latest advances in this area.

Ivan Mihajlin, Euler International Mathematical Institute, R401

We prove that there exists a function g such that the composition of the universal relation with g is significantly harder than just a universal relation. We also propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture. This relaxation is still strong enough to imply 𝐏 ̸⊆ NC¹ if proven.

Bruno Bauwens, HSE University, FCS, R401

Given a lossless bipartite expander, with a large left set and a smaller right set, we consider a dynamic matching problem. Left nodes arrive 1 by 1, and need to be associated to unique right nodes until the left node is retracted. We present an almost optimal matching algorithm. This algorithm can be used to construct 1-bit probes of smaller sizes than the best known ones. Moreover, the obtained bitprobes also support addition and retraction of elements. A second application is the construction of constant depth connectors, where we slightly improve the parameters.

Anastasia Sofronova,  PDMI RAS, R204

We prove an exponential lower bound on a proof system based on branching programs with bounded repetitions, (1, +k)-BPs, where the number of variables queried multiple times on one path is bounded by k = O(log n/log log n). Our hard examples encode that there is a source of the flow but no sink in an expander graph. We consider the problem of the search of the unsatisfied clause given an assignment. In suitable models, this is almost the same as proving that the formula is unsatisfiable. This problem does not have the structural properties that were used in classical lower bounds on functions for (1, +k)-BPs, so we introduce the new technique for obtaining lower bounds on Search problems for (1, +k)-BPs. This is a joint work with Dmitry Sokolov.

Alexander Kozachinskiy, HSE University, R204

We are interested in logarithmic-depth monotone formulas for the majority function. Unfortunaly, the only known explicit construction of such a formula is derived from the AKS sorting network. A drawback of that is the construction of the AKS sorting network is extremely complicated. I will report my attempts to obtain a more simple construction. Namely, I wil show how to construct an explicit polynomial-size O(log^{5/3}(n))-depth monotone circuit for the Majority function, without relying on the AKS-sorting.

Alexander Kulikov, St. Petersburg Department of Steklov Mathematical Institute, R204

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of this behavior is that the search space is enormous: the number of circuits of size s is s^s, the number of Boolean functions on n variables is 2^{2^n}.

In this talk, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. We report the results of experiments with various symmetric functions.

Nikolay Proskurin, HSE University, R204

In this paper we study the separation between two complexity measures: the degree of a Boolean function as a polynomial over the reals and the block sensitivity. We show that the upper bound on the largest possible separation between these two measures can be improved from $ d^2(f) \geq bs(f) $, established by Tal (ITCS ’13), to $ d^2(f) \geq (\sqrt{10} - 2)bs(f) $. As a corollary, we show that the similar upper bounds between some other complexity measures are not tight as well, for instance, we can improve the recent sensitivity conjecture result by Huang (Annals of Mathematics '19) $s^4(f) \geq bs(f) $ to $s^4(f) \geq (\sqrt{10} - 2)bs(f)$. Our techniques are based on the paper by Nisan and Szegedy (Comput. Complex. '94) and include more detailed analysis of a symmetrization polynomial. In our next result we show the same type of improvement for the separation between the approximate degree of a Boolean function and the block sensitivity: we show that $\deg_{1/3}^2(f) \geq \sqrt{6/101} bs(f)$ and improve the previous result by Nisan and Szegedy (Comput. Complex. '94) $ \deg_{1/3}(f) \geq \sqrt{bs(f)/6} $. In addition, we construct an example showing that the gap between the constants in the lower bound and in the known upper bound is less than $0.2$. In our last result we study the properties of a conjectured fully sensitive function on 10 variables of degree 4, existence of which would lead to improvement of the biggest known gap between these two measures. We prove that there is the only univariate polynomial that can be achieved by symmetrization of such a function by using the combination of interpolation and linear programming techniques.

Maksim Nikolaev, PDMI RAS, R204

Nikolay Vereshchagin, Moscow State University, HSE University, R204

We consider the network consisting of three nodes 1, 2, 3 connected by two open channels $1\to 2$ and $1\to 3$. The information present in the node 1 consists of four strings $x,y,z,w$. The nodes 2, 3 know $x,w$ and need to know $y,z$, respectively. We want to arrange transmission of information over the channels so that both nodes 2 and 3 learn what they need and the disclosure of information is as small as possible. By information disclosure we mean the amount of information in the strings transmitted through channels about $x,y,z,w$ (or about $x,w$). We are also interested in whether it is possible to minimize the disclosure of information and simultaneously minimize the length of words transferred through the channels.

Thomas Fernique, CNRS & Univ. Paris 13, R503

To cover the largest possible proportion of the Euclidean plane with disjoint two-by-two interior unit disks, the best solution is to center the disks on a triangular grid of side 2 (this is a 'compact hexagonal packing'). This problem can be generalized to higher dimensions, especially to dimension 3 with the famous Kepler conjecture. But it can also be generalized by considering disks of different sizes. This is the question that will interest us here, in particular for two sizes of disks. We propose an overview of the known results.

Dmitry Itsykson, PDMI RAS, R503

A canonical communication problem Search(F) is defined for every unsatisfiable CNF F: an assignment to the variables of F is distributed among the communicating parties, they are to find a clause of F falsified by this assignment. Lower bounds on the communication complexity of Search(F) imply tree-size lower bounds, rank lower bounds, and size-space tradeoffs for the formula F in a large class of proof systems. All known lower bounds on Search(F) are realized on ad-hoc formulas F (i.e. they were introduced specifically for these lower bounds). We introduce a new communication complexity approach that allows establishing proof complexity lower bounds for natural formulas. First, we demonstrate our approach for two-party communication and prove an exponential lower bound on the size of tree-like Res(+) refutations of the Perfect matching principle. Then we apply our approach to k-party communication complexity in the NOF model and obtain a lower bound on the randomized k-party communication complexity of Search(BPHP) w.r.t. to some natural partition of the variables, where BPHP is the bit pigeonhole principle. In particular, this lower bound implies that the bit pigeonhole requires exponential tree-like Th(k) proofs, where Th(k) is the semantic proof system operating with polynomial inequalities of degree at most k. The talk is based on the joint work with Artur Riazanov.

Artur Riazanov, St. Petersburg Department of V.A. Steklov Mathematical Institute, R503

The clique problem is one of the most basic NP-complete problems. There is a lot of indirect evidence that it is also hard in the average case. In this talk, we will explore this problem from the viewpoint of proof complexity. Approaching the average-case clique from this direction yields time complexity lower bounds for some classes of known algorithms (such as some SAT-solvers) and exposes many interesting challenges in the proof complexity itself. We will survey several known proof complexity lower bounds and discuss some open problems in the area. 

Michal Garlík, PDMI RAS, Euler International Mathematical Institute, R503

Does the existence of a short proof of A∨B, where A and B are propositional formulas that don’t share any variables, imply that there is a short proof of either A or B? This property of proof systems was defined in 2003 by Pudlák, who called it the feasible disjunction property (fdp) and observed it in all cases of proof systems that were known at the time to posses feasible interpolation (which is a related, though not provably, concept that was introduced by Krajíček for proving lower bounds). In particular, the resolution proof system has fdp, which is easy to see. Pudlák anticipated that the occurrence of fdp in stronger proof systems is unlikely, but until now fdp was not ruled out for any proof system. In this talk we discuss a recent work that gives a negative answer to the above question for a family of proof systems called R(k) that operate with disjunctions of k-conjunctions, and thus are situated just above resolution in strength. This involves proving size lower bounds on R(k) refutations of formulas called refutation statements, which are related to reflection principles.

Petr Smirnov, HSE University at Saint Petersburg, R503

We consider regular resolution refutations of unsatisfiable Tseitin formulas T(G, c) and bound the size S of such refutations via treewidth of underlying graph G. Prior to this work there were known two lower bounds of this type: S ≥ exp(Ω(tw(G) / log |V(G)|)) [Itsykson, Riazanov, Sagunov, Smirnov 2021] and S ≥ exp(Ω(tw(G) / Δ(G)) [de Colnet, Mengel 2021] (up to a polynomial factor). We improve the argument from the latter paper and prove a lower bound S ≥ exp(Ω(tw(G))) (up to a polynomial factor), which is stronger than previous bounds and tight in terms of graph treewidth and degrees.

Dmitry Sokolov, St. Petersburg State University, R503