Rishi Saket

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 32

Top Topics

Linear Threshold

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Yukti Makhija, Priyanka Agrawal, Rishi Saket, Aravindan Raghuveer
FRACTAL: Fine-Grained Scoring from Aggregate Text Labels. CoRR (2024)
Venkatesan Guruswami, Rishi Saket
Hardness of Learning Boolean Functions from Label Proportions. CoRR (2024)
Anand Brahmbhatt, Rishi Saket, Shreyas Havaldar, Anshul Nasery, Aravindan Raghuveer
Label Differential Privacy via Aggregation. CoRR (2023)
Venkatesan Guruswami, Rishi Saket
Hardness of Learning Boolean Functions from Label Proportions. FSTTCS (2023)
Anand Brahmbhatt, Rishi Saket, Aravindan Raghuveer
PAC Learning Linear Thresholds from Label Proportions. CoRR (2023)
Anand Brahmbhatt, Rishi Saket, Aravindan Raghuveer
PAC Learning Linear Thresholds from Label Proportions. NeurIPS (2023)
Jay Nandy, Jatin Chauhan, Rishi Saket, Aravindan Raghuveer
Non-Uniform Adversarial Perturbations for Discrete Tabular Datasets. CIKM (2023)
Anand Brahmbhatt, Mohith Pokala, Rishi Saket, Aravindan Raghuveer
LLP-Bench: A Large Scale Tabular Benchmark for Learning from Label Proportions. CoRR (2023)
Rishi Saket, Aravindan Raghuveer, Balaraman Ravindran
On Combining Bags to Better Learn from Label Proportions. AISTATS (2022)
Jatin Chauhan, Aravindan Raghuveer, Rishi Saket, Jay Nandy, Balaraman Ravindran
Multi-Variate Time Series Forecasting on Variable Subsets. CoRR (2022)
Jay Nandy, Rishi Saket, Prateek Jain, Jatin Chauhan, Balaraman Ravindran, Aravindan Raghuveer
Domain-Agnostic Contrastive Representations for Learning from Label Proportions. CIKM (2022)
Jatin Chauhan, Aravindan Raghuveer, Rishi Saket, Jay Nandy, Balaraman Ravindran
Multi-Variate Time Series Forecasting on Variable Subsets. KDD (2022)
Rishi Saket
Algorithms and Hardness for Learning Linear Thresholds from Label Proportions. NeurIPS (2022)
Rishi Saket
Learnability of Linear Thresholds from Label Proportions. NeurIPS (2021)
Suprovat Ghoshal, Rishi Saket
Hardness of learning DNFs using halfspaces. STOC (2021)
Rishi Saket, Nitin Singh, Pankaj Dayama, Vinayaka Pandit
Smart Contract Protocol for Authenticity and Compliance with Anonymity on Hyperledger Fabric. IEEE ICBC (2020)
Suprovat Ghoshal, Rishi Saket
Hardness of Learning DNFs using Halfspaces. Electron. Colloquium Comput. Complex. 26 (2019)
Suprovat Ghoshal, Rishi Saket
Hardness of Learning DNFs using Halfspaces. CoRR (2019)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of Learning Noisy Halfspaces using Polynomial Thresholds. COLT (2018)
Alina Ene, Viswanath Nagarajan, Rishi Saket
Approximation Algorithms for Stochastic k-TSP. FSTTCS (2017)
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket
On the Approximability of Digraph Ordering. Algorithmica 78 (4) (2017)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of learning noisy halfspaces using polynomial thresholds. CoRR (2017)
Subhash Khot, Rishi Saket
Colors. SIAM J. Comput. 46 (1) (2017)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of learning noisy halfspaces using polynomial thresholds. Electron. Colloquium Comput. Complex. 24 (2017)
Venkatesan Guruswami, Rishi Saket
Hardness of Rainbow Coloring Hypergraphs. Electron. Colloquium Comput. Complex. 24 (2017)
Jop Briët, Oded Regev, Rishi Saket
Tight Hardness of the Non-Commutative Grothendieck Problem. Theory Comput. 13 (1) (2017)
Venkatesan Guruswami, Rishi Saket
Hardness of Rainbow Coloring Hypergraphs. FSTTCS (2017)
Subhash Khot, Rishi Saket
Approximating CSPs using LP Relaxation. Electron. Colloquium Comput. Complex. 23 (2016)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms 12 (1) (2016)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the Hardness of Learning Sparse Parities. ESA (2016)
Subhash Khot, Rishi Saket
Hardness of Bipartite Expansion. ESA (2016)
Alina Ene, Viswanath Nagarajan, Rishi Saket
Approximation Algorithms for Stochastic k-TSP. CoRR (2016)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the hardness of learning sparse parities. Electron. Colloquium Comput. Complex. 22 (2015)
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs. SIAM J. Discret. Math. 29 (1) (2015)
Jop Briët, Oded Regev, Rishi Saket
Tight Hardness of the Non-commutative Grothendieck Problem. FOCS (2015)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the hardness of learning sparse parities. CoRR (2015)
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket
On the Approximability of Digraph Ordering. CoRR (2015)
Subhash Khot, Rishi Saket
Approximating CSPs Using LP Relaxation. ICALP (1) (2015)
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket
On the Approximability of Digraph Ordering. ESA (2015)
Subhash Khot, Rishi Saket
Colors. Electron. Colloquium Comput. Complex. 21 (2014)
Rishi Saket
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs. Computational Complexity Conference (2014)
Subhash Khot, Rishi Saket
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. SODA (2014)
Subhash Khot, Rishi Saket
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors. FOCS (2014)
Rishi Saket
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs. CoRR (2013)
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. Electron. Colloquium Comput. Complex. 20 (2013)
Subhash Khot, Rishi Saket
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. CoRR (2013)
Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber
The Approximability of the Binary Paintshop Problem. APPROX-RANDOM (2013)
Sushant Sachdeva, Rishi Saket
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. Computational Complexity Conference (2013)
Rishi Saket
A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure. CoRR (2013)
Inge Li Gørtz, Viswanath Nagarajan, Rishi Saket
Stochastic Vehicle Routing with Recourse CoRR (2012)
Rishi Saket, Maxim Sviridenko
New and Improved Bounds for the Minimum Set Cover Problem. APPROX-RANDOM (2012)
Inge Li Gørtz, Viswanath Nagarajan, Rishi Saket
Stochastic Vehicle Routing with Recourse. ICALP (1) (2012)
Subhash Khot, Rishi Saket
Hardness of Finding Independent Sets in Almost q-Colorable Graphs. FOCS (2012)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from some optimal geometric inapproximability results. SODA (2012)
Subhash Khot, Rishi Saket
On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci. 77 (1) (2011)
Sushant Sachdeva, Rishi Saket
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs CoRR (2011)
Sushant Sachdeva, Rishi Saket
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. APPROX-RANDOM (2011)
Parikshit Gopalan, Subhash Khot, Rishi Saket
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. SIAM J. Comput. 39 (6) (2010)
Subhash Khot, Preyas Popat, Rishi Saket
Approximate Lasserre Integrality Gap for Unique Games. APPROX-RANDOM (2010)
Rishi Saket
Quasi-Random PCP and Hardness of 2-Catalog Segmentation. FSTTCS (2010)
Venkatesan Guruswami, Rishi Saket
-Uniform Hypergraphs. ICALP (1) (2010)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from some optimal geometric inapproximability results. Electron. Colloquium Comput. Complex. 17 (2010)
Subhash Khot, Rishi Saket
SDP Integrality Gaps with Local ell_1-Embeddability. FOCS (2009)
Subhash Khot, Rishi Saket
On hardness of learning intersection of two halfspaces. STOC (2008)
Subhash Khot, Rishi Saket
Hardness of Minimizing and Learning DNF Expressions. FOCS (2008)
Subhash Khot, Rishi Saket
Hardness of Embedding Metric Spaces of Equal Size. APPROX-RANDOM (2007)
Parikshit Gopalan, Subhash Khot, Rishi Saket
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. FOCS (2007)
Parikshit Gopalan, Subhash Khot, Rishi Saket
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Electron. Colloquium Comput. Complex. 14 (073) (2007)
Rishi Saket, Nicolas Navet
Frame packing algorithms for automotive applications. J. Embed. Comput. 2 (1) (2006)
Subhash Khot, Rishi Saket
A 3-Query Non-Adaptive PCP with Perfect Completeness. Computational Complexity Conference (2006)
Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi
Integrality gaps for sparsest cut and minimum linear arrangement problems. STOC (2006)