6 Search Results for "Podolskii, Vladimir"


Document
Constant-Depth Sorting Networks

Authors: Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
In this paper, we address sorting networks that are constructed from comparators of arity k > 2. I.e., in our setting the arity of the comparators - or, in other words, the number of inputs that can be sorted at the unit cost - is a parameter. We study its relationship with two other parameters - n, the number of inputs, and d, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for majority functions from majority gates of lower fan-in. Motivated by these questions, we initiate the studies of lower bounds for constant-depth sorting networks. More precisely, we consider sorting networks of constant depth d and estimate the minimal k for which there is such a network with comparators of arity k. We prove tight lower bounds for d ≤ 4. More precisely, for depths d = 1,2 we observe that k = n. For d = 3 we show that k = ⌈n/2⌉. As our main result, we show that for d = 4 the minimal arity becomes sublinear: k = Θ(n^{2/3}). This contrasts with the case of majority circuits, in which k = O(n^{2/3}) is achievable already for depth d = 3. To prove these results, we develop a new combinatorial technique based on the notion of access to cells of a sorting network.

Cite as

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii. Constant-Depth Sorting Networks. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{dobrokhotovamaikova_et_al:LIPIcs.ITCS.2023.43,
  author =	{Dobrokhotova-Maikova, Natalia and Kozachinskiy, Alexander and Podolskii, Vladimir},
  title =	{{Constant-Depth Sorting Networks}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.43},
  URN =		{urn:nbn:de:0030-drops-175468},
  doi =		{10.4230/LIPIcs.ITCS.2023.43},
  annote =	{Keywords: Sorting networks, constant depth, lower bounds, threshold circuits}
}
Document
Polynomial Threshold Functions for Decision Lists

Authors: Vladimir Podolskii and Nikolay V. Proskurin

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
For S ⊆ {0,1}ⁿ a Boolean function f : S → {-1,1} is a polynomial threshold function (PTF) of degree d and weight W if there is a polynomial p with integer coefficients of degree d and with sum of absolute coefficients W such that f(x) = sign p(x) for all x ∈ S. We study a representation of decision lists as PTFs over Boolean cubes {0,1}ⁿ and over Hamming balls {0,1}ⁿ_{≤ k}. As our first result, we show that for all d = O((n/(log n))^{1/3}) any decision list over {0,1}ⁿ can be represented by a PTF of degree d and weight 2^O(n/d²). This improves the result by Klivans and Servedio [Adam R. Klivans and Rocco A. Servedio, 2006] by a log² d factor in the exponent of the weight. Our bound is tight for all d = O((n/(log n))^{1/3}) due to the matching lower bound by Beigel [Richard Beigel, 1994]. For decision lists over a Hamming ball {0,1}ⁿ_{≤ k} we show that the upper bound on weight above can be drastically improved to n^O(√k) for d = Θ(√k). We also show that similar improvement is not possible for smaller degrees by proving the lower bound W = 2^Ω(n/d²) for all d = O(√k).

Cite as

Vladimir Podolskii and Nikolay V. Proskurin. Polynomial Threshold Functions for Decision Lists. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{podolskii_et_al:LIPIcs.ISAAC.2022.52,
  author =	{Podolskii, Vladimir and Proskurin, Nikolay V.},
  title =	{{Polynomial Threshold Functions for Decision Lists}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.52},
  URN =		{urn:nbn:de:0030-drops-173372},
  doi =		{10.4230/LIPIcs.ISAAC.2022.52},
  annote =	{Keywords: Threshold function, decision list, Hamming ball}
}
Document
Multiparty Karchmer - Wigderson Games and Threshold Circuits

Authors: Alexander Kozachinskiy and Vladimir Podolskii

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)


Abstract
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 formula for Majority function, consisting only of 3-bit majority gates and variables. This resolves a conjecture of Cohen et al. (CRYPTO 2013).

Cite as

Alexander Kozachinskiy and Vladimir Podolskii. Multiparty Karchmer - Wigderson Games and Threshold Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kozachinskiy_et_al:LIPIcs.CCC.2020.24,
  author =	{Kozachinskiy, Alexander and Podolskii, Vladimir},
  title =	{{Multiparty Karchmer - Wigderson Games and Threshold Circuits}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.24},
  URN =		{urn:nbn:de:0030-drops-125767},
  doi =		{10.4230/LIPIcs.CCC.2020.24},
  annote =	{Keywords: Karchmer-Wigderson Games, Threshold Circuits, threshold gates, majority function}
}
Document
Complexity of Linear Operators

Authors: Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
Let A in {0,1}^{n x n} be a matrix with z zeroes and u ones and x be an n-dimensional vector of formal variables over a semigroup (S, o). How many semigroup operations are required to compute the linear operator Ax? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute Ax using O(u) semigroup operations. The main question studied in this paper is: can Ax be computed using O(z) semigroup operations? We prove that in general this is not possible: there exists a matrix A in {0,1}^{n x n} with exactly two zeroes in every row (hence z=2n) whose complexity is Theta(n alpha(n)) where alpha(n) is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an O(z) upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two n x n matrices over an arbitrary semiring in O(n^2) time if one of these matrices is a 0/1-matrix with O(n) zeroes (i.e., a complement of a sparse matrix).

Cite as

Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii. Complexity of Linear Operators. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kulikov_et_al:LIPIcs.ISAAC.2019.17,
  author =	{Kulikov, Alexander S. and Mikhailin, Ivan and Mokhov, Andrey and Podolskii, Vladimir},
  title =	{{Complexity of Linear Operators}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.17},
  URN =		{urn:nbn:de:0030-drops-115137},
  doi =		{10.4230/LIPIcs.ISAAC.2019.17},
  annote =	{Keywords: algorithms, linear operators, commutativity, range queries, circuit complexity, lower bounds, upper bounds}
}
Document
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

Authors: Alexander S. Kulikov and Vladimir V. Podolskii

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
We study the following computational problem: for which values of k, the majority of n bits 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 MAJ_k o MAJ_k. We observe that the minimum value of k for which there exists a MAJ_k o MAJ_k circuit that has high correlation with the majority of n bits is equal to Theta(sqrt(n)). We then show that for a randomized MAJ_k o 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 MAJ_k o MAJ_k circuit computes the majority of n bits correctly on all inputs, then k <= 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 MAJ_n correctly on all inputs.

Cite as

Alexander S. Kulikov and Vladimir V. Podolskii. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{kulikov_et_al:LIPIcs.STACS.2017.49,
  author =	{Kulikov, Alexander S. and Podolskii, Vladimir V.},
  title =	{{Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.49},
  URN =		{urn:nbn:de:0030-drops-69832},
  doi =		{10.4230/LIPIcs.STACS.2017.49},
  annote =	{Keywords: circuit complexity, computational complexity, threshold, majority, lower bound, upper bound}
}
Document
Tropical Effective Primary and Dual Nullstellens"atze

Authors: Dima Grigoriev and Vladimir V. Podolskii

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
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 tropical Nullstellensatz and moreover we show effective formulation of this theorem. Nullstellensatz is a next natural step in building algebraic theory of tropical polynomials and effective version is relevant for computational aspects of this field.

Cite as

Dima Grigoriev and Vladimir V. Podolskii. Tropical Effective Primary and Dual Nullstellens"atze. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 379-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{grigoriev_et_al:LIPIcs.STACS.2015.379,
  author =	{Grigoriev, Dima and Podolskii, Vladimir V.},
  title =	{{Tropical Effective Primary and Dual Nullstellens"atze}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{379--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.379},
  URN =		{urn:nbn:de:0030-drops-49286},
  doi =		{10.4230/LIPIcs.STACS.2015.379},
  annote =	{Keywords: tropical algebra, tropical geometry, Nullstellensatz}
}
  • Refine by Author
  • 4 Podolskii, Vladimir
  • 2 Kozachinskiy, Alexander
  • 2 Kulikov, Alexander S.
  • 2 Podolskii, Vladimir V.
  • 1 Dobrokhotova-Maikova, Natalia
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Models of computation
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 circuit complexity
  • 2 lower bounds
  • 1 Hamming ball
  • 1 Karchmer-Wigderson Games
  • 1 Nullstellensatz
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017
  • 1 2019
  • 1 2020
  • 1 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail