Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Anastasia Sofronova and Dmitry Sokolov. Branching Programs with Bounded Repetitions and Flow Formulas. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 17:1-17:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{sofronova_et_al:LIPIcs.CCC.2021.17, author = {Sofronova, Anastasia and Sokolov, Dmitry}, title = {{Branching Programs with Bounded Repetitions and Flow Formulas}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {17:1--17:25}, 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.17}, URN = {urn:nbn:de:0030-drops-142915}, doi = {10.4230/LIPIcs.CCC.2021.17}, annote = {Keywords: proof complexity, branching programs, bounded repetitions, lower bounds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 89:1-89:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2021.89, author = {Filmus, Yuval and Meir, Or and Tal, Avishay}, title = {{Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {89:1--89:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.89}, URN = {urn:nbn:de:0030-drops-136281}, doi = {10.4230/LIPIcs.ITCS.2021.89}, annote = {Keywords: De Morgan formulas, KRW Conjecture, shrinkage, random restrictions, random projections, bounded depth circuits, constant depth circuits, formula complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness Magnification near State-Of-The-Art Lower Bounds. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 27:1-27:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.27, author = {Oliveira, Igor Carboni and Pich, J\'{a}n and Santhanam, Rahul}, title = {{Hardness Magnification near State-Of-The-Art Lower Bounds}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {27:1--27:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.27}, URN = {urn:nbn:de:0030-drops-108494}, doi = {10.4230/LIPIcs.CCC.2019.27}, annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Stasys Jukna and Andrzej Lingas. Lower Bounds for DeMorgan Circuits of Bounded Negation Width. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 41:1-41:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{jukna_et_al:LIPIcs.STACS.2019.41, author = {Jukna, Stasys and Lingas, Andrzej}, title = {{Lower Bounds for DeMorgan Circuits of Bounded Negation Width}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {41:1--41: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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.41}, URN = {urn:nbn:de:0030-drops-102801}, doi = {10.4230/LIPIcs.STACS.2019.41}, annote = {Keywords: Boolean circuits, monotone circuits, lower bounds} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, and Alexander S. Kulikov. On the Limits of Gate Elimination. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovnev_et_al:LIPIcs.MFCS.2016.46, author = {Golovnev, Alexander and Hirsch, Edward A. and Knop, Alexander and Kulikov, Alexander S.}, title = {{On the Limits of Gate Elimination}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {46:1--46:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.46}, URN = {urn:nbn:de:0030-drops-64593}, doi = {10.4230/LIPIcs.MFCS.2016.46}, annote = {Keywords: circuit complexity, lower bounds, gate elimination} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Stefan Kratsch and Manuel Sorge. On Kernelization and Approximation for the Vector Connectivity Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kratsch_et_al:LIPIcs.IPEC.2015.377, author = {Kratsch, Stefan and Sorge, Manuel}, title = {{On Kernelization and Approximation for the Vector Connectivity Problem}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {377--388}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.377}, URN = {urn:nbn:de:0030-drops-55985}, doi = {10.4230/LIPIcs.IPEC.2015.377}, annote = {Keywords: parameterized complexity, kernelization, approximation} }
Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Static Analysis for Logic-based Dynamic Programs. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 308-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{schwentick_et_al:LIPIcs.CSL.2015.308, author = {Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas}, title = {{Static Analysis for Logic-based Dynamic Programs}}, booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)}, pages = {308--324}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-90-3}, ISSN = {1868-8969}, year = {2015}, volume = {41}, editor = {Kreutzer, Stephan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.308}, URN = {urn:nbn:de:0030-drops-54221}, doi = {10.4230/LIPIcs.CSL.2015.308}, annote = {Keywords: Dynamic descriptive complexity, algorithmic problems, emptiness, history independence, consistency} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Joshua Brody and Mario Sanchez. Dependent Random Graphs and Multi-Party Pointer Jumping. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 606-624, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2015.606, author = {Brody, Joshua and Sanchez, Mario}, title = {{Dependent Random Graphs and Multi-Party Pointer Jumping}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {606--624}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.606}, URN = {urn:nbn:de:0030-drops-53266}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.606}, annote = {Keywords: random graphs, communication complexity, number-on-the-forehead model, pointer jumping} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Siyao Guo and Ilan Komargodski. Negation-Limited Formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 850-866, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{guo_et_al:LIPIcs.APPROX-RANDOM.2015.850, author = {Guo, Siyao and Komargodski, Ilan}, title = {{Negation-Limited Formulas}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {850--866}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.850}, URN = {urn:nbn:de:0030-drops-53400}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.850}, annote = {Keywords: Negation complexity, De Morgan formulas, Shrinkage} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Ishay Haviv and Oded Regev. The List-Decoding Size of Fourier-Sparse Boolean Functions. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{haviv_et_al:LIPIcs.CCC.2015.58, author = {Haviv, Ishay and Regev, Oded}, title = {{The List-Decoding Size of Fourier-Sparse Boolean Functions}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {58--71}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.58}, URN = {urn:nbn:de:0030-drops-50600}, doi = {10.4230/LIPIcs.CCC.2015.58}, annote = {Keywords: Fourier-sparse functions, list-decoding, learning theory, property testing} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Alex Samorodnitsky, Ilya Shkredov, and Sergey Yekhanin. Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 347-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{samorodnitsky_et_al:LIPIcs.CCC.2015.347, author = {Samorodnitsky, Alex and Shkredov, Ilya and Yekhanin, Sergey}, title = {{Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {347--364}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.347}, URN = {urn:nbn:de:0030-drops-50703}, doi = {10.4230/LIPIcs.CCC.2015.347}, annote = {Keywords: Matrix rigidity, linear codes, Kolmogorov width} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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.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} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Anat Ganor and Ran Raz. Space Pseudorandom Generators by Communication Complexity Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 692-703, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{ganor_et_al:LIPIcs.APPROX-RANDOM.2014.692, author = {Ganor, Anat and Raz, Ran}, title = {{Space Pseudorandom Generators by Communication Complexity Lower Bounds}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {692--703}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.692}, URN = {urn:nbn:de:0030-drops-47324}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.692}, annote = {Keywords: Communication complexity, Logspace, Pseudorandom generator} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 721-736, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2014.721, author = {G\"{o}\"{o}s, Mika and Watson, Thomas}, title = {{Communication Complexity of Set-Disjointness for All Probabilities}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {721--736}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.721}, URN = {urn:nbn:de:0030-drops-47342}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.721}, annote = {Keywords: Communication Complexity, Set-Disjointness, All Probabilities} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Stasys Jukna. Graphs and Circuits: Some Further Remarks. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{jukna:DagSemProc.06111.8, author = {Jukna, Stasys}, title = {{Graphs and Circuits: Some Further Remarks}}, booktitle = {Complexity of Boolean Functions}, pages = {1--16}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.8}, URN = {urn:nbn:de:0030-drops-6218}, doi = {10.4230/DagSemProc.06111.8}, annote = {Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits} }
Feedback for Dagstuhl Publishing