Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
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)
@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} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
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)
@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} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
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)
@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} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
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)
@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} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
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)
@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} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
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)
@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} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)
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)
@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} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
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)
@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}, }
Feedback for Dagstuhl Publishing