All reports by Author Vladimir Podolskii:

__
TR20-017
| 18th February 2020
__

Alexander Kozachinskiy, Vladimir Podolskii#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

__
TR19-002
| 31st December 2018
__

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii#### Complexity of Linear Operators

__
TR18-174
| 19th October 2018
__

Anastasiya Chistopolskaya, Vladimir Podolskii#### Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

__
TR17-184
| 29th November 2017
__

Vladimir Podolskii, Alexander A. Sherstov#### Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

__
TR16-158
| 9th October 2016
__

Alexander Kulikov, Vladimir Podolskii#### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

__
TR13-021
| 5th February 2013
__

Kristoffer Arnsfelt Hansen, Vladimir Podolskii#### Polynomial threshold functions and Boolean threshold circuits

Alexander Kozachinskiy, Vladimir Podolskii

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

Anastasiya Chistopolskaya, Vladimir Podolskii

We prove a new lower bound on the parity decision tree complexity $D_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $D_{\oplus}(f)\geq k+1$.

This lower bound is ... more >>>

Vladimir Podolskii, Alexander A. Sherstov

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>

Alexander Kulikov, Vladimir Podolskii

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>