Source author record

Vladimir V. Podolskii

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Logic in Computer Science math.AG Symbolic Computation

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

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 the minimum value of $k$ for which there exists a $\text{MAJ}_k \circ \text{MAJ}_k$ circuit that has high correlation with the majority of $n$ bits is equal to $Θ(n^{1/2})$ . We then show that for a randomized $\text{MAJ}_k \circ \text{MAJ}_k$ circuit computing the majority of $n$ input bits with high probability for every input, the minimum value of $k$ is equal to $n^{2/3+o(1)}$ . We show a worst case lower bound: if a $\text{MAJ}_k \circ \text{MAJ}_k$ circuit computes the majority of $n$ bits correctly on all inputs, then $k\geq n^{13/19+o(1)}$ . This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth $3$ circuits we show that a circuit with $k= O(n^{2/3})$ can compute $\text{MAJ}_n$ correctly on all inputs.

preprint2016arXiv

Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries

We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, which matches the optimal combined complexity.

preprint2015arXiv

Circuit Complexity Meets Ontology-Based Data Access

Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach query answering proceeds through a reformulation of a given query into a new one which can be answered without any use of theory. Thus the problem reduces to the standard database setting. However, the size of the query may increase substantially during the reformulation. In this survey we review a recently developed framework on proving lower and upper bounds on the size of this reformulation by employing methods and results from Boolean circuit complexity.

preprint2015arXiv

Tropical Effective Primary and Dual Nullstellensätze

Tropical algebra is an emerging field with a number of applications in various areas of mathematics. In many of these applications appeal to tropical polynomials allows to study properties of mathematical objects such as algebraic varieties and algebraic curves from the computational point of view. This makes it important to study both mathematical and computational aspects of tropical polynomials. In this paper we prove a tropical Nullstellensatz and moreover we show an effective formulation of this theorem. Nullstellensatz is a natural step in building algebraic theory of tropical polynomials and its effective version is relevant for computational aspects of this field. On our way we establish a simple formulation of min-plus and tropical linear dualities. We also observe a close connection between tropical and min-plus polynomial systems.

preprint2013arXiv

Lower Bound on Weights of Large Degree Threshold Functions

An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate} for a Boolean function $f$ of $n$ variables if for all $x \in \zoon$ $f(x)=1$ if and only if $p(x)\geq 0$ . The \emph{weight} of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if we fix some function and some threshold degree. We prove $2^{Ω(2^{2n/5})}$ lower bound on this value. The best previous bound was $2^{Ω(2^{n/8})}$ (Podolskii, 2009). In addition we present substantially simpler proof of the weaker $2^{Ω(2^{n/4})}$ lower bound. This proof is conceptually similar to other proofs of the bounds on weights of nonlinear threshold gates, but avoids a lot of technical details arising in other proofs. We hope that this proof will help to show the ideas behind the construction used to prove these lower bounds.

preprint2012arXiv

Complexity of tropical and min-plus linear prevarieties

A tropical (or min-plus) semiring is a set $\mathbb{Z}$ (or $\mathbb{Z \cup \{\infty\}}$ ) endowed with two operations: $\oplus$ , which is just usual minimum, and $\odot$ , which is usual addition. In tropical algebra the vector $x$ is a solution to a polynomial $g_1(x) \oplus g_2(x) \oplus...\oplus g_k(x)$ , where $g_i(x)$ 's are tropical monomials, if the minimum in $\min_i(g_{i}(x))$ is attained at least twice. In min-plus algebra solutions of systems of equations of the form $g_1(x)\oplus...\oplus g_k(x) = h_1(x)\oplus...\oplus h_l(x)$ are studied. In this paper we consider computational problems related to tropical linear system. We show that the solvability problem (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$ ) and the problem of deciding the equivalence of two linear systems (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$ ) are equivalent under polynomial-time reduction to mean payoff games and are also equivalent to analogous problems in min-plus algebra. In particular, all these problems belong to $\mathsf{NP} \cap \mathsf{coNP}$ . Thus we provide a tight connection of computational aspects of tropical linear algebra with mean payoff games and min-plus linear algebra. On the other hand we show that computing the dimension of the solution space of a tropical linear system and of a min-plus linear system are $\mathsf{NP}$ -complete. We also extend some of our results to the systems of min-plus linear inequalities.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.