No photo of Subhash Khot

View Scopus Profile

Subhash Khot

Silver Professor; Professor of Computer Science

    20002023

    Research activity per year

    If you made any changes in Pure these will be visible here soon.
    Filter
    Conference contribution

    Search results

    • 2023

      Improved Monotonicity Testers via Hypercube Embeddings

      Braverman, M., Khot, S., Kindler, G. & Minzer, D., Jan 1 2023, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Kalai, Y. T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 25. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 251).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2022

      Almost Polynomial Factor Inapproximability for Parameterized k-Clique

      Karthik, C. S. & Khot, S., Jul 1 2022, 37th Computational Complexity Conference, CCC 2022. Lovett, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 6. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 234).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • An Invariance Principle for the Multi-slice, with Applications

      Braverman, M., Khot, S., Lifshitz, N. & Minzer, D., 2022, Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE Computer Society, p. 228-236 9 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-February).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On approximability of satisfiable k-CSPs: I

      Bhangale, A., Khot, S. & Minzer, D., Sep 6 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 976-988 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

      Open Access
    • 2021

      On rich 2-to-1 games

      Braverman, M., Khot, S. & Minzer, D., Feb 1 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Optimal inapproximability of satisfiable k-LIN over non-abelian groups

      Bhangale, A. & Khot, S., Jun 15 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1615-1628 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

      Open Access

    • Theorems of KKL, friedgut, and talagrand via random restrictions and log-sobolev inequality

      Kelman, E., Khot, S., Kindler, G., Minzer, D. & Safra, M., Feb 1 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 26. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2020

      Simultaneous Max-Cut is harder to approximate than Max-Cut

      Bhangale, A. & Khot, S., Jul 1 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 9. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2019

      Improved 3LIN hardness via linear label cover

      Harsha, P., Khot, S., Lee, E. & Thiruvenkatachari, D., Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 9. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • UG-hardness to NP-hardness by losing half

      Bhangale, A. & Khot, S., Jul 1 2019, 34th Computational Complexity Conference, CCC 2019. Shpilka, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 137).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2018

      An improved dictatorship test with perfect completeness

      Bhangale, A., Khot, S. & Thiruvenkatachari, D., Jan 1 2018, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017. Lokam, S. & Ramanujam, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 15. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 93).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Near-optimal approximation algorithm for simultaneous Max-cut

      Bhangale, A., Khot, S., Kopparty, S., Sachdeva, S. & Thiruvenkatachari, D., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 1407-1425 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On non-optimally expanding sets in grassmann graphs

      Dinur, I., Khot, S., Kindler, G., Minzer, D. & Safra, M., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 1193-1206 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Pseudorandom sets in Grassmann graph have near-perfect expansion

      Khot, S., Minzer, D. & Safra, M., Nov 30 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 592-601 10 p. 8555140. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Towards a proof of the 2-to-1 games conjecture?

      Dinur, I., Khot, S., Kindler, G., Minzer, D. & Safra, M., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 1297-1306 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2017

      On Independent Sets, 2-to-2 Games, and Grassmann Graphs

      Khot, S., Minzer, D. & Safra, M., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 576-589 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2016

      An Ō(n) queries adaptive tester for unateness

      Khot, S. & Shinkar, I., Sep 1 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Jansen, K., Mathieu, C., Rolim, J. D. P. & Umans, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 60).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Candidate hard unique game

      Khot, S. & Moshkovitz, D., Jun 19 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 63-76 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of bipartite expansion

      Khot, S. & Saket, R., Aug 1 2016, 24th Annual European Symposium on Algorithms, ESA 2016. Zaroliagis, C. & Sankowski, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 55. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 57).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On hardness of approximating the parameterized clique problem

      Khot, S. & Shinkar, I., Jan 14 2016, ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, Inc, p. 37-45 9 p. (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2015

      Approximating CSPs using LP relaxation

      Khot, S. & Saket, R., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). Springer Verlag, p. 822-833 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9134).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On Monotonicity Testing and Boolean Isoperimetric Type Theorems

      Khot, S., Minzer, D. & Safra, M., Dec 11 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 52-58 7 p. 7354387. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2014

      A characterization of strong approximation resistance

      Khot, S., Tulsiani, M. & Worah, P., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 634-643 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of approximation

      Khot, S., 2014, Plenary Lectures and Ceremonies. Jang, S. Y., Kim, Y. R., Lee, D-W. & Yie, I. (eds.). KYUNG MOON SA Co. Ltd., p. 711-728 18 p. (Proceeding of the International Congress of Mathematicans, ICM 2014; vol. 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors

      Khot, S. & Saket, R., Dec 7 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 206-215 10 p. 6979005. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs

      Khot, S. & Saket, R., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 1607-1625 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • The complexity of somewhat approximation resistant predicates

      Khot, S., Tulsiani, M. & Worah, P., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 689-700 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2013

      A characterization of approximation resistance for even k-partite CSPs

      Austrin, P. & Khot, S., 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 187-196 10 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Towards an optimal query efficient PCP?

      Khot, S., Safra, M. & Tulsiani, M., 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 173-186 14 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2012

      2 log1-εn hardness for the closest vector problem with preprocessing

      Khot, S. A., Popat, P. & Vishnoi, N. K., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 277-288 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of finding independent sets in almost q-colorable graphs

      Khot, S. & Saket, R., 2012, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 380-389 10 p. 6375316

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2011

      A simple deterministic reduction for the gap minimum distance of code problem

      Austrin, P. & Khot, S., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. p. 474-485 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6755 LNCS, no. PART 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • A two prover one round game with strong soundness

      Khot, S. & Safra, M., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 648-657 10 p. 6108226. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • NP-hardness of approximately solving linear equations over reals

      Khot, S. & Moshkovitz, D., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 413-419 7 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2010

      Approximate Lasserre integrality gap for unique games

      Khot, S., Popat, P. & Saket, R., 2010, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. p. 298-311 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6302 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of finding independent sets in almost 3-colorable graphs

      Dinur, I., Khot, S., Perkins, W. & Safra, M., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 212-221 10 p. 5670828. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Inapproximability of hypergraph vertex cover and applications to scheduling problems

      Bansal, N. & Khot, S., 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 250-261 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Inapproximability of NP-complete problems, discrete fourier analysis, and geometry

      Khot, S., 2010, Proceedings of the International Congress of Mathematicians 2010, ICM 2010. p. 2676-2697 22 p. (Proceedings of the International Congress of Mathematicians 2010, ICM 2010).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On the unique games conjecture

      Khot, S., 2010, Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010. p. 99-121 23 p. 5497893. (Proceedings of the Annual IEEE Conference on Computational Complexity).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • SDP gaps for 2-to-1 and other label-cover variants

      Guruswami, V., Khot, S., O'Donnell, R., Popat, P., Tulsiani, M. & Wu, Y., 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 617-628 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Sharp kernel clustering algorithms and their associated Grothendieck inequalities

      Khot, S. & Naor, A., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. p. 664-683 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2009

      Inapproximability of vertex cover and independent set in bounded degree graphs

      Austrin, P., Khot, S. & Safra, M., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 74-80 7 p. 5231231. (Proceedings of the Annual IEEE Conference on Computational Complexity).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Optimal long code test with one free bit

      Bansal, N. & Khot, S., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 453-462 10 p. 5438609. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • SDP integrality gaps with local ℓ1-embeddability

      Khot, S. & Saket, R., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 565-574 10 p. 5438596. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2008

      Approximate kernel clustering

      Khot, S. & Naor, A., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 561-570 10 p. 4690989. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of minimizing and learning DNF expressions

      Khot, S. & Saket, R., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 231-240 10 p. 4690957. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • On hardness of learning intersection of two halfspaces

      Khot, S. & Saket, R., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 345-353 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • 2007

      Approximation algorithms for the max-min allocation problem

      Khot, S. & Ponnuswami, A. K., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 204-217 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of embedding metric spaces of equal size

      Khot, S. & Sake, R., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 218-227 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    • Hardness of reconstructing multivariate polynomials over finite fields

      Gopalan, P., Khot, S. & Saket, R., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 349-359 11 p. 4389506. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Your message has successfully been sent.
    Your message was not sent due to an error.