H-Index & Metrics Top Publications

H-Index & Metrics

Discipline name H-index Citations Publications World Ranking National Ranking
Computer Science H-index 35 Citations 8,334 101 World Ranking 6032 National Ranking 2880
Mathematics H-index 35 Citations 8,467 108 World Ranking 1465 National Ranking 644

Research.com Recognitions

Awards & Achievements

2017 - Fellow of the Royal Society, United Kingdom

2016 - Fellow of the MacArthur Foundation

2014 - Rolf Nevanlinna Prize "For his prescient definition of the “Unique Games” problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry."[12]

2010 - National Science Foundation Alan T. Waterman Award Computer Science

2006 - Fellow of Alfred P. Sloan Foundation

Overview

What is he best known for?

The fields of study he is best known for:

  • Combinatorics
  • Discrete mathematics
  • Algebra

His scientific interests lie mostly in Combinatorics, Discrete mathematics, Unique games conjecture, Approximation algorithm and Conjecture. His study on Hardness of approximation, Binary logarithm and Boolean function is often connected to Set theory as part of broader study in Combinatorics. His Discrete mathematics research is multidisciplinary, incorporating elements of Computational complexity theory and Graph theory.

His Unique games conjecture research is multidisciplinary, incorporating perspectives in Graph, Grothendieck inequality and Maximum cut. His work in Approximation algorithm addresses subjects such as Combinatorial optimization, which are connected to disciplines such as Monotone polygon and Submodular set function. His Vertex cover study combines topics from a wide range of disciplines, such as Theory of computing and Constant factor.

His most cited work include:

  • On the power of unique 2-prover 1-round games (810 citations)
  • Vertex cover might be hard to approximate to within 2-ε (586 citations)
  • Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? (473 citations)

What are the main themes of his work throughout his whole career to date?

His primary areas of study are Combinatorics, Discrete mathematics, Unique games conjecture, Hardness of approximation and Approximation algorithm. His Combinatorics study incorporates themes from Computational complexity theory and Constant. The study incorporates disciplines such as Function and Fraction in addition to Discrete mathematics.

His Unique games conjecture study also includes

  • Maximum cut which intersects with area such as Rounding and Grothendieck inequality,
  • Embedding most often made with reference to Reduction. Subhash Khot combines subjects such as PCP theorem, Bipartite graph and Finite field with his study of Hardness of approximation. His Approximation algorithm study deals with Time complexity intersecting with Vertex.

He most often published in these fields:

  • Combinatorics (77.19%)
  • Discrete mathematics (64.33%)
  • Unique games conjecture (28.07%)

What were the highlights of his more recent work (between 2016-2021)?

  • Combinatorics (77.19%)
  • Discrete mathematics (64.33%)
  • Boolean function (9.36%)

In recent papers he was focusing on the following fields of study:

The scientist’s investigation covers issues in Combinatorics, Discrete mathematics, Boolean function, Conjecture and Function. His Combinatorics study typically links adjacent topics like Small set. His Boolean function research incorporates themes from Property testing and Mathematical proof.

His specific area of interest is Conjecture, where Subhash Khot studies Unique games conjecture. His Function research focuses on Integer and how it connects with Variable. He has included themes like Vertex, Maximum cut, Rounding and Approximation algorithm in his Time complexity study.

Between 2016 and 2021, his most popular works were:

  • On independent sets, 2-to-2 games, and Grassmann graphs (27 citations)
  • Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. (25 citations)
  • Towards a proof of the 2-to-1 games conjecture? (18 citations)

In his most recent research, the most cited papers focused on:

  • Algebra
  • Combinatorics
  • Real number

Subhash Khot mainly focuses on Combinatorics, Graph, Small set, Conjecture and Vertex cover. As part of his studies on Combinatorics, Subhash Khot often connects relevant areas like Pseudorandom number generator. He integrates many fields, such as Small set, Completeness, Linearity, Imperfect and Cover, in his works.

The various areas that Subhash Khot examines in his Vertex cover study include Feedback vertex set, Independent set and Vertex. Subhash Khot connects Maximal independent set with Discrete mathematics in his study.

This overview was generated by a machine learning system which analysed the scientist’s body of work. If you have any feedback, you can contact us here.

Top Publications

On the power of unique 2-prover 1-round games

Subhash Khot.
symposium on the theory of computing (2002)

1271 Citations

Vertex cover might be hard to approximate to within 2-ε

Subhash Khot;Oded Regev.
Journal of Computer and System Sciences (2008)

784 Citations

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

Subhash Khot;Guy Kindler;Elchanan Mossel;Ryan O’Donnell.
SIAM Journal on Computing (2007)

694 Citations

The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

S.A. Khot;N.K. Vishnoi.
foundations of computer science (2005)

439 Citations

Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique

Subhash Khot.
SIAM Journal on Computing (2006)

282 Citations

Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring

S. Khot.
international conference on cluster computing (2001)

257 Citations

Hardness of approximating the shortest vector problem in lattices

Subhash Khot.
Journal of the ACM (2005)

232 Citations

Near-optimal lower bounds on the multi-party communication complexity of set disjointness

A. Chakrabarti;S. Khot;Xiaodong Sun.
conference on computational complexity (2003)

229 Citations

Parameterized Complexity of Finding Subgraphs with Hereditary Properties

Subhash Khot;Venkatesh Raman.
computing and combinatorics conference (2000)

190 Citations

Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

S. Khot.
foundations of computer science (2004)

188 Citations

Profile was last updated on December 6th, 2021.
Research.com Ranking is based on data retrieved from the Microsoft Academic Graph (MAG).
The ranking h-index is inferred from publications deemed to belong to the considered discipline.

If you think any of the details on this page are incorrect, let us know.

Contact us

Top Scientists Citing Subhash Khot

Venkatesan Guruswami

Venkatesan Guruswami

Carnegie Mellon University

Publications: 69

Ryan O'Donnell

Ryan O'Donnell

Carnegie Mellon University

Publications: 56

Assaf Naor

Assaf Naor

Princeton University

Publications: 50

Elchanan Mossel

Elchanan Mossel

MIT

Publications: 48

Oded Regev

Oded Regev

Courant Institute of Mathematical Sciences

Publications: 45

Saket Saurabh

Saket Saurabh

University of Bergen

Publications: 37

Moses Charikar

Moses Charikar

Stanford University

Publications: 35

Rocco A. Servedio

Rocco A. Servedio

Columbia University

Publications: 33

Uriel Feige

Uriel Feige

Weizmann Institute of Science

Publications: 31

Robert Krauthgamer

Robert Krauthgamer

Weizmann Institute of Science

Publications: 30

Vitaly Feldman

Vitaly Feldman

Apple (United States)

Publications: 30

Boaz Barak

Boaz Barak

Tel Aviv University

Publications: 28

Venkatesh Raman

Venkatesh Raman

Institute of Mathematical Sciences

Publications: 27

Luca Trevisan

Luca Trevisan

Bocconi University

Publications: 27

David P. Woodruff

David P. Woodruff

Carnegie Mellon University

Publications: 26

Something went wrong. Please try again later.