LIPIcs, Volume 200
CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference)
Editors: Valentine Kabanets
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. Synergy Between Circuit Obfuscation and Circuit Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{impagliazzo_et_al:LIPIcs.APPROX/RANDOM.2023.31, author = {Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya}, title = {{Synergy Between Circuit Obfuscation and Circuit Minimization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {31:1--31:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.31}, URN = {urn:nbn:de:0030-drops-188569}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.31}, annote = {Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Improved Learning from Kolmogorov Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {12:1--12:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.12}, URN = {urn:nbn:de:0030-drops-182825}, doi = {10.4230/LIPIcs.CCC.2023.12}, annote = {Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity} }
Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{blaser_et_al:DagRep.12.9.41, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, title = {{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)}}, pages = {41--59}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.9.41}, URN = {urn:nbn:de:0030-drops-178092}, doi = {10.4230/DagRep.12.9.41}, annote = {Keywords: (de-)randomization, algebra, circuits, coding, computational complexity} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16, author = {Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {16:1--16:60}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16}, URN = {urn:nbn:de:0030-drops-165785}, doi = {10.4230/LIPIcs.CCC.2022.16}, annote = {Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Valentine Kabanets. LIPIcs, Volume 200, CCC 2021, Complete Volume. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1-1290, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Proceedings{kabanets:LIPIcs.CCC.2021, title = {{LIPIcs, Volume 200, CCC 2021, Complete Volume}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {1--1290}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021}, URN = {urn:nbn:de:0030-drops-142732}, doi = {10.4230/LIPIcs.CCC.2021}, annote = {Keywords: LIPIcs, Volume 200, CCC 2021, Complete Volume} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Valentine Kabanets. Front Matter, Table of Contents, Preface, Conference Organization. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kabanets:LIPIcs.CCC.2021.0, author = {Kabanets, Valentine}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.0}, URN = {urn:nbn:de:0030-drops-142745}, doi = {10.4230/LIPIcs.CCC.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Gil Cohen and Tal Yankovitz. Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1:1-1:57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.CCC.2021.1, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {1:1--1:57}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.1}, URN = {urn:nbn:de:0030-drops-142750}, doi = {10.4230/LIPIcs.CCC.2021.1}, annote = {Keywords: Locally decodable codes, Locally correctable codes} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Nati Linial and Adi Shraibman. An Improved Protocol for the Exactly-N Problem. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 2:1-2:8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{linial_et_al:LIPIcs.CCC.2021.2, author = {Linial, Nati and Shraibman, Adi}, title = {{An Improved Protocol for the Exactly-N Problem}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {2:1--2:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.2}, URN = {urn:nbn:de:0030-drops-142760}, doi = {10.4230/LIPIcs.CCC.2021.2}, annote = {Keywords: Communication complexity, Number-On-the-Forehead, Corner-free sets} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Dmitry Itsykson and Artur Riazanov. Proof Complexity of Natural Formulas via Communication Arguments. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 3:1-3:34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{itsykson_et_al:LIPIcs.CCC.2021.3, author = {Itsykson, Dmitry and Riazanov, Artur}, title = {{Proof Complexity of Natural Formulas via Communication Arguments}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {3:1--3:34}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.3}, URN = {urn:nbn:de:0030-drops-142773}, doi = {10.4230/LIPIcs.CCC.2021.3}, annote = {Keywords: bit pigeonhole principle, disjointness, multiparty communication complexity, perfect matching, proof complexity, randomized communication complexity, Resolution over linear equations, tree-like proofs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{A Lower Bound on Determinantal Complexity}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4}, URN = {urn:nbn:de:0030-drops-142781}, doi = {10.4230/LIPIcs.CCC.2021.4}, annote = {Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Mark Braverman and Dor Minzer. Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 5:1-5:48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{braverman_et_al:LIPIcs.CCC.2021.5, author = {Braverman, Mark and Minzer, Dor}, title = {{Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {5:1--5:48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.5}, URN = {urn:nbn:de:0030-drops-142796}, doi = {10.4230/LIPIcs.CCC.2021.5}, annote = {Keywords: PCP, Parallel Repetition, Tilings} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the Power and Limitations of Branch and Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 6:1-6:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{fleming_et_al:LIPIcs.CCC.2021.6, author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Impagliazzo, Russell and Pitassi, Toniann and Robere, Robert and Tan, Li-Yang and Wigderson, Avi}, title = {{On the Power and Limitations of Branch and Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {6:1--6:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.6}, URN = {urn:nbn:de:0030-drops-142809}, doi = {10.4230/LIPIcs.CCC.2021.6}, annote = {Keywords: Proof Complexity, Integer Programming, Cutting Planes, Branch and Cut, Stabbing Planes} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Prerona Chatterjee. Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 7:1-7:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chatterjee:LIPIcs.CCC.2021.7, author = {Chatterjee, Prerona}, title = {{Separating ABPs and Some Structured Formulas in the Non-Commutative Setting}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {7:1--7:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.7}, URN = {urn:nbn:de:0030-drops-142812}, doi = {10.4230/LIPIcs.CCC.2021.7}, annote = {Keywords: Non-Commutative Formulas, Lower Bound, Separating ABPs and Formulas} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Alexander Golovnev and Ishay Haviv. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{golovnev_et_al:LIPIcs.CCC.2021.8, author = {Golovnev, Alexander and Haviv, Ishay}, title = {{The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.8}, URN = {urn:nbn:de:0030-drops-142829}, doi = {10.4230/LIPIcs.CCC.2021.8}, annote = {Keywords: Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs} }
Feedback for Dagstuhl Publishing