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
Tight hardness of the non-commutative grothendieck problem
- Jop Briët
- Oded Regev
- et al.
- 2017
- Theory of Computing
Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors
- Subhash Khot
- Rishi Saket
- 2017
- SIAM Journal on Computing
On the Approximability of Digraph Ordering
- Sreyash Kenkre
- Vinayaka Pandit
- et al.
- 2016
- Algorithmica
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
Inapproximability of minimum vertex cover on k-uniform k-partite hypergraphs
- Venkatesan Guruswami
- Sushant Sachdeva
- et al.
- 2015
- SIAM Journal on Discrete Mathematics
Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors
- Subhash Khot
- Rishi Saket
- 2014
- FOCS 2014