10 Search Results for "Shen, Alexander"


Document
NP-Hardness of Circuit Minimization for Multi-Output Functions

Authors: Rahul Ilango, Bruno Loff, and Igor C. Oliveira

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


Abstract
Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive. In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f : {0,1}^n → {0,1}^m is NP-hard under many-one polynomial-time randomized reductions. Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators. Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are NP-hard under deterministic reductions. In particular, unless 𝖯 = 𝖭𝖯, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.

Cite as

Rahul Ilango, Bruno Loff, and Igor C. Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 22:1-22:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ilango_et_al:LIPIcs.CCC.2020.22,
  author =	{Ilango, Rahul and Loff, Bruno and Oliveira, Igor C.},
  title =	{{NP-Hardness of Circuit Minimization for Multi-Output Functions}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{22:1--22:36},
  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.22},
  URN =		{urn:nbn:de:0030-drops-125744},
  doi =		{10.4230/LIPIcs.CCC.2020.22},
  annote =	{Keywords: MCSP, circuit minimization, communication complexity, Boolean circuit}
}
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
Information Distance Revisited

Authors: Bruno Bauwens

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
We consider the notion of information distance between two objects x and y introduced by Bennett, Gács, Li, Vitanyi, and Zurek [C. H. Bennett et al., 1998] as the minimal length of a program that computes x from y as well as computing y from x, and study different versions of this notion. In the above paper, it was shown that the prefix version of information distance equals max (K(x|y),K(y|x)) up to additive logarithmic terms. It was claimed by Mahmud [Mahmud, 2009] that this equality holds up to additive O(1)-precision. We show that this claim is false, but does hold if the distance is at least logarithmic. This implies that the original definition provides a metric on strings that are at superlogarithmically separated.

Cite as

Bruno Bauwens. Information Distance Revisited. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bauwens:LIPIcs.STACS.2020.46,
  author =	{Bauwens, Bruno},
  title =	{{Information Distance Revisited}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.46},
  URN =		{urn:nbn:de:0030-drops-119071},
  doi =		{10.4230/LIPIcs.STACS.2020.46},
  annote =	{Keywords: Kolmogorov complexity, algorithmic information distance}
}
Document
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Authors: Julien Destombes and Andrei Romashchenko

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on Z^2 with very low block complexity: the number of globally admissible patterns of size n x n grows only as a polynomial in n.

Cite as

Julien Destombes and Andrei Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{destombes_et_al:LIPIcs.STACS.2019.23,
  author =	{Destombes, Julien and Romashchenko, Andrei},
  title =	{{Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.23},
  URN =		{urn:nbn:de:0030-drops-102624},
  doi =		{10.4230/LIPIcs.STACS.2019.23},
  annote =	{Keywords: Sofic shifts, Block complexity, Kolmogorov complexity}
}
Document
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension

Authors: Gleb Posobin and Alexander Shen

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
Consider a bit string x of length n and Kolmogorov complexity alpha n (for some alpha<1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [Harry Buhrman et al., 2005]. What happens with the complexity of x when we randomly change each bit independently with some probability tau? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change considered in [Harry Buhrman et al., 2005]. The amount of the increase depends on x (strings of the same complexity could behave differently). We give exact lower and upper bounds for this increase (with o(n) precision). The same technique is used to prove the results about the (effective Hausdorff) dimension of infinite sequences. We show that random change increases the dimension with probability 1, and provide an optimal lower bound for the dimension of the changed sequence. We also improve a result from [Noam Greenberg et al., 2018] and show that for every sequence omega of dimension alpha there exists a strongly alpha-random sequence omega' such that the Besicovitch distance between omega and omega' is 0. The proofs use the combinatorial and probabilistic reformulations of complexity statements and the technique that goes back to Ahlswede, Gács and Körner [Ahlswede et al., 1976].

Cite as

Gleb Posobin and Alexander Shen. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{posobin_et_al:LIPIcs.STACS.2019.57,
  author =	{Posobin, Gleb and Shen, Alexander},
  title =	{{Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.57},
  URN =		{urn:nbn:de:0030-drops-102969},
  doi =		{10.4230/LIPIcs.STACS.2019.57},
  annote =	{Keywords: Kolmogorov complexity, effective Hausdorff dimension, random noise}
}
Document
Plain Stopping Time and Conditional Complexities Revisited

Authors: Mikhail Andreev, Gleb Posobin, and Alexander Shen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)<n; (e) as maxC^X(x) where C^X(z) is plain Kolmogorov complexity of z relative to oracle X and the maximum is taken over all extensions X of x. We also show that some of these equivalent definitions become non-equivalent in the more general setting where the condition y and the object x may differ, and answer an open question from Chernov, Hutter and Schmidhuber [Alexey V. Chernov et al., 2007].

Cite as

Mikhail Andreev, Gleb Posobin, and Alexander Shen. Plain Stopping Time and Conditional Complexities Revisited. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{andreev_et_al:LIPIcs.MFCS.2018.2,
  author =	{Andreev, Mikhail and Posobin, Gleb and Shen, Alexander},
  title =	{{Plain Stopping Time and Conditional Complexities Revisited}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.2},
  URN =		{urn:nbn:de:0030-drops-95842},
  doi =		{10.4230/LIPIcs.MFCS.2018.2},
  annote =	{Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory}
}
Document
Limit complexities revisited

Authors: Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is known) equals $KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with $mathbf{0'$-oracle. Then we use the same argument to prove similar results for prefix complexity (and also improve results of (Muchnik, 1987) about limit frequencies), a priori probability on binary tree and measure of effectively open sets. As a by-product, we get a criterion of $mathbf{0'$ Martin-L"of randomness (called also $2$-randomness) proved in (Miller, 2004): a sequence $omega$ is $2$-random if and only if there exists $c$ such that any prefix $x$ of $omega$ is a prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the 1960ies this property was suggested in (Kolmogorov, 1968) as one of possible randomness definitions; its equivalence to $2$-randomness was shown in (Miller, 2004) while proving another $2$-randomness criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many prefixes $x$ of $omega$. Finally, we show that the low-basis theorem can be used to get alternative proofs for these results and to improve the result about effectively open sets; this stronger version implies the $2$-randomness criterion mentioned in the previous sentence.

Cite as

Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2008.1335,
  author =	{Bienvenu, Laurent and Muchnik, Andrej and Shen, Alexander and Veraschagin, Nikolay},
  title =	{{Limit complexities revisited}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{73--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1335},
  URN =		{urn:nbn:de:0030-drops-13350},
  doi =		{10.4230/LIPIcs.STACS.2008.1335},
  annote =	{Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis}
}
Document
Combinatorial proof of Muchnik's theorem

Authors: Alexander Shen

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)


Abstract
Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts: 1) we construct a graph that allows large online matchings (main part) 2) we use this graph to prove the theorem The question about online matching could be interesting in itself.

Cite as

Alexander Shen. Combinatorial proof of Muchnik's theorem. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.5,
  author =	{Shen, Alexander},
  title =	{{Combinatorial proof of Muchnik's theorem}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.5},
  URN =		{urn:nbn:de:0030-drops-6258},
  doi =		{10.4230/DagSemProc.06051.5},
  annote =	{Keywords: Matching conditional descriptions Kolmogorov complexity}
}
Document
Multisource Algorithmic Information Theory

Authors: Alexander Shen

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)


Abstract
Multisource information theory is well known in Shannon setting. It studies the possibilities of information transfer through a network with limited capacities. Similar questions could be studied for algorithmic information theory and provide a framework for several known results and interesting questions.

Cite as

Alexander Shen. Multisource Algorithmic Information Theory. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.9,
  author =	{Shen, Alexander},
  title =	{{Multisource Algorithmic Information Theory}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.9},
  URN =		{urn:nbn:de:0030-drops-6267},
  doi =		{10.4230/DagSemProc.06051.9},
  annote =	{Keywords: Kolmogorov complexity multisource information theory}
}
Document
Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)

Authors: Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)


Copy BibTex To Clipboard

@TechReport{durand_et_al:DagSemRep.377,
  author =	{Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.},
  title =	{{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{377},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.377},
  URN =		{urn:nbn:de:0030-drops-152578},
  doi =		{10.4230/DagSemRep.377},
}
  • Refine by Author
  • 6 Shen, Alexander
  • 2 Posobin, Gleb
  • 1 Andreev, Mikhail
  • 1 Bauwens, Bruno
  • 1 Bienvenu, Laurent
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Information theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 5 Kolmogorov complexity
  • 1 2-randomness
  • 1 Block complexity
  • 1 Boolean circuit
  • 1 Karchmer-Wigderson Games
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2020
  • 2 2006
  • 2 2019
  • 1 2003
  • 1 2008
  • 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