Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer. Improved Monotonicity Testers via Hypercube Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 25:1-25:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.25, author = {Braverman, Mark and Khot, Subhash and Kindler, Guy and Minzer, Dor}, title = {{Improved Monotonicity Testers via Hypercube Embeddings}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {25:1--25:24}, 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.25}, URN = {urn:nbn:de:0030-drops-175285}, doi = {10.4230/LIPIcs.ITCS.2023.25}, annote = {Keywords: Property Testing, Monotonicity Testing, Isoperimetric Inequalities} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Karthik C. S. and Subhash Khot. Almost Polynomial Factor Inapproximability for Parameterized k-Clique. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 6:1-6:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{karthikc.s._et_al:LIPIcs.CCC.2022.6, author = {Karthik C. S. and Khot, Subhash}, title = {{Almost Polynomial Factor Inapproximability for Parameterized k-Clique}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {6:1--6:21}, 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.6}, URN = {urn:nbn:de:0030-drops-165680}, doi = {10.4230/LIPIcs.CCC.2022.6}, annote = {Keywords: Parameterized Complexity, k-clique, Hardness of Approximation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Ronen Eldan and Dana Moshkovitz. Reduction from Non-Unique Games to Boolean Unique Games. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 64:1-64:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{eldan_et_al:LIPIcs.ITCS.2022.64, author = {Eldan, Ronen and Moshkovitz, Dana}, title = {{Reduction from Non-Unique Games to Boolean Unique Games}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {64:1--64:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.64}, URN = {urn:nbn:de:0030-drops-156605}, doi = {10.4230/LIPIcs.ITCS.2022.64}, annote = {Keywords: Unique Games Conjecture, hyperplane encoding, concentration of measure, low degree testing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kelman_et_al:LIPIcs.ITCS.2021.26, author = {Kelman, Esty and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli}, title = {{Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {26:1--26:17}, 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.26}, URN = {urn:nbn:de:0030-drops-135657}, doi = {10.4230/LIPIcs.ITCS.2021.26}, annote = {Keywords: Fourier Analysis, Hypercontractivity, Log-Sobolev Inequality} }
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 169, 35th Computational Complexity Conference (CCC 2020)
Amey Bhangale and Subhash Khot. Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 9:1-9:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2020.9, author = {Bhangale, Amey and Khot, Subhash}, title = {{Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {9:1--9:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.9}, URN = {urn:nbn:de:0030-drops-125610}, doi = {10.4230/LIPIcs.CCC.2020.9}, annote = {Keywords: Simultaneous CSPs, Unique Games hardness, Max-Cut} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari. Improved 3LIN Hardness via Linear Label Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{harsha_et_al:LIPIcs.APPROX-RANDOM.2019.9, author = {Harsha, Prahladh and Khot, Subhash and Lee, Euiwoong and Thiruvenkatachari, Devanathan}, title = {{Improved 3LIN Hardness via Linear Label Cover}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {9:1--9:16}, 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.9}, URN = {urn:nbn:de:0030-drops-112245}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.9}, annote = {Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error} }
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 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Amey Bhangale, Subhash Khot, and Devanathan Thiruvenkatachari. An Improved Dictatorship Test with Perfect Completeness. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 15:1-15:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bhangale_et_al:LIPIcs.FSTTCS.2017.15, author = {Bhangale, Amey and Khot, Subhash and Thiruvenkatachari, Devanathan}, title = {{An Improved Dictatorship Test with Perfect Completeness}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {15:1--15:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.15}, URN = {urn:nbn:de:0030-drops-83854}, doi = {10.4230/LIPIcs.FSTTCS.2017.15}, annote = {Keywords: Property Testing, Distatorship Test, Fourier Analysis} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Subhash Khot and Igor Shinkar. An ~O(n) Queries Adaptive Tester for Unateness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 37:1-37:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{khot_et_al:LIPIcs.APPROX-RANDOM.2016.37, author = {Khot, Subhash and Shinkar, Igor}, title = {{An \textasciitildeO(n) Queries Adaptive Tester for Unateness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {37:1--37:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.37}, URN = {urn:nbn:de:0030-drops-66603}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.37}, annote = {Keywords: property testing, boolean functions, unateness} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Subhash Khot. Hardness of Approximation (Invited Talk). In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{khot:LIPIcs.ICALP.2016.3, author = {Khot, Subhash}, title = {{Hardness of Approximation}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.3}, URN = {urn:nbn:de:0030-drops-63395}, doi = {10.4230/LIPIcs.ICALP.2016.3}, annote = {Keywords: NP-completeness, Approximation algorithms, Inapproximability, Probabilistically Checkable Proofs, Discrete Fourier analysis} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Subhash Khot and Rishi Saket. Hardness of Bipartite Expansion. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 55:1-55:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{khot_et_al:LIPIcs.ESA.2016.55, author = {Khot, Subhash and Saket, Rishi}, title = {{Hardness of Bipartite Expansion}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {55:1--55:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.55}, URN = {urn:nbn:de:0030-drops-63971}, doi = {10.4230/LIPIcs.ESA.2016.55}, annote = {Keywords: inapproximability, bipartite expansion, PCP, submodular minimization} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Subhash Khot. On Approximation Resistance of Predicates (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, p. 19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{khot:LIPIcs.FSTTCS.2013.19, author = {Khot, Subhash}, title = {{On Approximation Resistance of Predicates}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {19--19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.19}, URN = {urn:nbn:de:0030-drops-44011}, doi = {10.4230/LIPIcs.FSTTCS.2013.19}, annote = {Keywords: Approximation resistance, Hardness of approximation, Probabilistically checkable proofs, Constraint satisfaction problem} }
Feedback for Dagstuhl Publishing