Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Vladimir Podolskii:

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Complexity of Linear Operators

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 >>>

TR18-174 | 19th October 2018
Anastasiya Chistopolskaya, Vladimir Podolskii

Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

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 >>>

TR17-184 | 29th November 2017
Vladimir Podolskii, Alexander A. Sherstov

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

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 >>>

TR16-158 | 9th October 2016
Alexander Kulikov, Vladimir Podolskii

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

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 >>>

TR13-021 | 5th February 2013
Kristoffer Arnsfelt Hansen, Vladimir Podolskii

Polynomial threshold functions and Boolean threshold circuits

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 >>>

ISSN 1433-8092 | Imprint