Hardness of learning DNFs using halfspaces
- Suprovat Ghoshal
- Rishi Saket
- 2021
- STOC 2021
Conference paper
Publications
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
Conference paperTight hardness of the non-commutative grothendieck problem
- Jop Briët
- Oded Regev
- et al.
- 2017
- Theory of Computing
PaperHardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors
- Subhash Khot
- Rishi Saket
- 2017
- SIAM Journal on Computing
PaperOn the Approximability of Digraph Ordering
- Sreyash Kenkre
- Vinayaka Pandit
- et al.
- 2016
- Algorithmica
PaperOn the hardness of learning sparse parities
- Arnab Bhattacharyya
- Ameet Gadekar
- et al.
- 2016
- ESA 2016
Conference paperHardness of bipartite expansion
- Subhash Khot
- Rishi Saket
- 2016
- ESA 2016
Conference paperTight Hardness of the Non-commutative Grothendieck Problem
- Jop Briot
- Oded Regev
- et al.
- 2015
- FOCS 2015
Conference paperInapproximability of minimum vertex cover on k-uniform k-partite hypergraphs
- Venkatesan Guruswami
- Sushant Sachdeva
- et al.
- 2015
- SIAM Journal on Discrete Mathematics
PaperHardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors
- Subhash Khot
- Rishi Saket
- 2014
- FOCS 2014
Conference paper