Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Roy Gotlib and Tali Kaufman. Fine Grained Analysis of High Dimensional Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 49:1-49:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{gotlib_et_al:LIPIcs.APPROX/RANDOM.2023.49, author = {Gotlib, Roy and Kaufman, Tali}, title = {{Fine Grained Analysis of High Dimensional Random Walks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {49:1--49:22}, 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.49}, URN = {urn:nbn:de:0030-drops-188740}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.49}, annote = {Keywords: High Dimensional Expanders, High Dimensional Random Walks, Local Spectral Expansion, Local to Global, Trickling Down} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yahli Hecht, Dor Minzer, and Muli Safra. NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hecht_et_al:LIPIcs.APPROX/RANDOM.2023.51, author = {Hecht, Yahli and Minzer, Dor and Safra, Muli}, title = {{NP-Hardness of Almost Coloring Almost 3-Colorable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {51:1--51:12}, 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.51}, URN = {urn:nbn:de:0030-drops-188761}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.51}, annote = {Keywords: PCP, Hardness of approximation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan. A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 38:1-38:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chuzhoy_et_al:LIPIcs.ITCS.2023.38, author = {Chuzhoy, Julia and Dalirrooyfard, Mina and Grinberg, Vadim and Tan, Zihan}, title = {{A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {38:1--38:23}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.38}, URN = {urn:nbn:de:0030-drops-175411}, doi = {10.4230/LIPIcs.ITCS.2023.38}, annote = {Keywords: Hardness of Approximation, Densest k-Subgraph} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Irit Dinur. Expanders in Higher Dimensions (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dinur:LIPIcs.FSTTCS.2022.4, author = {Dinur, Irit}, title = {{Expanders in Higher Dimensions}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.4}, URN = {urn:nbn:de:0030-drops-173967}, doi = {10.4230/LIPIcs.FSTTCS.2022.4}, annote = {Keywords: Expanders} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Fotis Iliopoulos. Improved Bounds for Coloring Locally Sparse Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{iliopoulos:LIPIcs.APPROX/RANDOM.2021.39, author = {Iliopoulos, Fotis}, title = {{Improved Bounds for Coloring Locally Sparse Hypergraphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {39:1--39:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.39}, URN = {urn:nbn:de:0030-drops-147328}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.39}, annote = {Keywords: hypergaph coloring, semi-random method, locally sparse, random hypergraphs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Mark Braverman, Subhash Khot, and Dor Minzer. On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 27:1-27:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{braverman_et_al:LIPIcs.ITCS.2021.27, author = {Braverman, Mark and Khot, Subhash and Minzer, Dor}, title = {{On Rich 2-to-1 Games}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {27:1--27:20}, 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.27}, URN = {urn:nbn:de:0030-drops-135666}, doi = {10.4230/LIPIcs.ITCS.2021.27}, annote = {Keywords: PCP, Unique-Games, Perfect Completeness} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani. Explicit SoS Lower Bounds from High-Dimensional Expanders. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 38:1-38:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2021.38, author = {Dinur, Irit and Filmus, Yuval and Harsha, Prahladh and Tulsiani, Madhur}, title = {{Explicit SoS Lower Bounds from High-Dimensional Expanders}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {38:1--38:16}, 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.38}, URN = {urn:nbn:de:0030-drops-135774}, doi = {10.4230/LIPIcs.ITCS.2021.38}, annote = {Keywords: High-dimensional expanders, sum-of-squares, integrality gaps} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.34, author = {Guruswami, Venkatesan and Opr\v{s}al, Jakub and Sandeep, Sai}, title = {{Revisiting Alphabet Reduction in Dinur’s PCP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {34:1--34:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.34}, URN = {urn:nbn:de:0030-drops-126372}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.34}, annote = {Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Elazar Goldenberg and Karthik C. S.. Hardness Amplification of Optimization Problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 1:1-1:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{goldenberg_et_al:LIPIcs.ITCS.2020.1, author = {Goldenberg, Elazar and Karthik C. S.}, title = {{Hardness Amplification of Optimization Problems}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.1}, URN = {urn:nbn:de:0030-drops-116863}, doi = {10.4230/LIPIcs.ITCS.2020.1}, annote = {Keywords: hardness amplification, average case complexity, direct product, optimization problems, fine-grained complexity, TFNP} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Orr Paradise. Smooth and Strong PCPs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 2:1-2:41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{paradise:LIPIcs.ITCS.2020.2, author = {Paradise, Orr}, title = {{Smooth and Strong PCPs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {2:1--2:41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.2}, URN = {urn:nbn:de:0030-drops-116875}, doi = {10.4230/LIPIcs.ITCS.2020.2}, annote = {Keywords: Interactive and probabilistic proof systems, Probabilistically checkable proofs, Hardness of approximation} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Irit Dinur and Konstantin Golubev. Direct Sum Testing: The General Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 40:1-40:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dinur_et_al:LIPIcs.APPROX-RANDOM.2019.40, author = {Dinur, Irit and Golubev, Konstantin}, title = {{Direct Sum Testing: The General Case}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {40:1--40:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.40}, URN = {urn:nbn:de:0030-drops-112554}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.40}, annote = {Keywords: property testing, direct sum, tensor product} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Amey Bhangale and Subhash Khot. UG-Hardness to NP-Hardness by Losing Half. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 3:1-3:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2019.3, author = {Bhangale, Amey and Khot, Subhash}, title = {{UG-Hardness to NP-Hardness by Losing Half}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {3:1--3:20}, 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.3}, URN = {urn:nbn:de:0030-drops-108258}, doi = {10.4230/LIPIcs.CCC.2019.3}, annote = {Keywords: NP-hardness, Inapproximability, Unique Games Conjecture} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi. From Local to Robust Testing via Agreement Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2019.29, author = {Dinur, Irit and Harsha, Prahladh and Kaufman, Tali and Ron-Zewi, Noga}, title = {{From Local to Robust Testing via Agreement Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {29:1--29:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.29}, URN = {urn:nbn:de:0030-drops-101221}, doi = {10.4230/LIPIcs.ITCS.2019.29}, annote = {Keywords: Local testing, Robust testing, Agreement testing, Affine-invariant codes, Lifted codes} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Irit Dinur, Oded Goldreich, and Tom Gur. Every Set in P Is Strongly Testable Under a Suitable Encoding. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 30:1-30:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2019.30, author = {Dinur, Irit and Goldreich, Oded and Gur, Tom}, title = {{Every Set in P Is Strongly Testable Under a Suitable Encoding}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.30}, URN = {urn:nbn:de:0030-drops-101234}, doi = {10.4230/LIPIcs.ITCS.2019.30}, annote = {Keywords: Probabilistically checkable proofs, property testing} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Nader H. Bshouty and Waseem Makhoul. On Polynomial Time Constructions of Minimum Height Decision Tree. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 34:1-34:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{h.bshouty_et_al:LIPIcs.ISAAC.2018.34, author = {H. Bshouty, Nader and Makhoul, Waseem}, title = {{On Polynomial Time Constructions of Minimum Height Decision Tree}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {34:1--34:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.34}, URN = {urn:nbn:de:0030-drops-99824}, doi = {10.4230/LIPIcs.ISAAC.2018.34}, annote = {Keywords: Decision Tree, Minimal Depth, Approximation algorithms} }
Feedback for Dagstuhl Publishing