Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Noah G. Singer. Oblivious Algorithms for the Max-kAND Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 15:1-15:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{singer:LIPIcs.APPROX/RANDOM.2023.15, author = {Singer, Noah G.}, title = {{Oblivious Algorithms for the Max-kAND Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {15:1--15:19}, 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.15}, URN = {urn:nbn:de:0030-drops-188409}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.15}, annote = {Keywords: streaming algorithm, approximation algorithm, constraint satisfaction problem (CSP), factor-revealing linear program} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 42:1-42:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2022.42, author = {Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter}, title = {{Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {42:1--42:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.42}, URN = {urn:nbn:de:0030-drops-171642}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.42}, annote = {Keywords: Planted clique, Average-case complexity, Spectral refutation, Random matrix theory} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7, author = {Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan}, title = {{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {7:1--7:17}, 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.7}, URN = {urn:nbn:de:0030-drops-165695}, doi = {10.4230/LIPIcs.CCC.2022.7}, annote = {Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pravesh K. Kothari and Peter Manohar. A Stress-Free Sum-Of-Squares Lower Bound for Coloring. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 23:1-23:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kothari_et_al:LIPIcs.CCC.2021.23, author = {Kothari, Pravesh K. and Manohar, Peter}, title = {{A Stress-Free Sum-Of-Squares Lower Bound for Coloring}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {23:1--23:21}, 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.23}, URN = {urn:nbn:de:0030-drops-142978}, doi = {10.4230/LIPIcs.CCC.2021.23}, annote = {Keywords: Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Local Testability in the Non-Signaling Setting. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 26:1-26:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2020.26, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Local Testability in the Non-Signaling Setting}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {26:1--26:37}, 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.26}, URN = {urn:nbn:de:0030-drops-117112}, doi = {10.4230/LIPIcs.ITCS.2020.26}, annote = {Keywords: non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 25:1-25:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2019.25, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {25:1--25: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.25}, URN = {urn:nbn:de:0030-drops-101188}, doi = {10.4230/LIPIcs.ITCS.2019.25}, annote = {Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing Linearity against Non-Signaling Strategies. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 17:1-17:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chiesa_et_al:LIPIcs.CCC.2018.17, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Testing Linearity against Non-Signaling Strategies}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {17:1--17:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.17}, URN = {urn:nbn:de:0030-drops-88731}, doi = {10.4230/LIPIcs.CCC.2018.17}, annote = {Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 39:1-39:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chiesa_et_al:LIPIcs.APPROX-RANDOM.2017.39, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Axis-Parallel Tests for Tensor Product Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {39:1--39:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.39}, URN = {urn:nbn:de:0030-drops-75882}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.39}, annote = {Keywords: tensor product codes, locally testable codes, low-degree testing, extremal graph theory} }
Feedback for Dagstuhl Publishing