Hardness of learning DNFs using halfspaces
- Suprovat Ghoshal
- Rishi Saket
- 2021
- STOC 2021
Publications
Date
Featured collections
Popular topics
13 results for Rishi Saket
Smart Contract Protocol for Authenticity and Compliance with Anonymity on Hyperledger Fabric
- Rishi Saket
- Nitin Singh
- et al.
- 2020
- ICBC 2020
On the hardness of learning sparse parities
- Arnab Bhattacharyya
- Ameet Gadekar
- et al.
- 2016
- ESA 2016
Hardness of bipartite expansion
- Subhash Khot
- Rishi Saket
- 2016
- ESA 2016
Tight Hardness of the Non-commutative Grothendieck Problem
- Jop Briot
- Oded Regev
- et al.
- 2015
- FOCS 2015
Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors
- Subhash Khot
- Rishi Saket
- 2014
- FOCS 2014
Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover
- Sushant Sachdeva
- Rishi Saket
- 2013
- CCC 2013
Hardness of finding independent sets in almost q-colorable graphs
- Subhash Khot
- Rishi Saket
- 2012
- FOCS 2012
Integrality gaps for sparsest cut and minimum linear arrangement problems
- Nikhil R. Devanur
- Subhash A. Khot
- et al.
- 2006
- STOC 2006
On the Approximability of Digraph Ordering
- Sreyash Kenkre
- Vinayaka Pandit
- et al.
- 2016
- Algorithmica