Rishi Saket

Aravindan Raghuveer

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Hardness of Learning Boolean Functions from Label Proportions.

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Non-Uniform Adversarial Perturbations for Discrete Tabular Datasets.

[BibT_eX]

[DOI]

Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, 2023

2022

Algorithms and Hardness for Learning Linear Thresholds from Label Proportions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Multi-Variate Time Series Forecasting on Variable Subsets.

[BibT_eX]

[DOI]

Proceedings of the KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14, 2022

Domain-Agnostic Contrastive Representations for Learning from Label Proportions.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022

On Combining Bags to Better Learn from Label Proportions.

[BibT_eX]

[DOI]

Aravindan Raghuveer

Balaraman Ravindran

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Learnability of Linear Thresholds from Label Proportions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Smart Contract Protocol for Authenticity and Compliance with Anonymity on Hyperledger Fabric.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Blockchain and Cryptocurrency, 2020

2019

Hardness of Learning DNFs using Halfspaces.

[BibT_eX]

[DOI]

Suprovat Ghoshal

Electron. Colloquium Comput. Complex., 2019

2017

Tight Hardness of the Non-Commutative Grothendieck Problem.

[BibT_eX]

[DOI]

Jop Briët

Oded Regev

Theory Comput., 2017

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2(log n)Ømega(1) Colors.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Hardness of Rainbow Coloring Hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Hardness of learning noisy halfspaces using polynomial thresholds.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Suprovat Ghoshal

Electron. Colloquium Comput. Complex., 2017

On the Approximability of Digraph Ordering.

[BibT_eX]

[DOI]

Algorithmica, 2017

Approximation Algorithms for Stochastic k-TSP.

[BibT_eX]

[DOI]

Alina Ene

Viswanath Nagarajan

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Bypassing UGC from Some Optimal Geometric Inapproximability Results.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Approximating CSPs using LP Relaxation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Hardness of Bipartite Expansion.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs.

[BibT_eX]

[DOI]

Sushant Sachdeva

SIAM J. Discret. Math., 2015

On the hardness of learning sparse parities.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure.

[BibT_eX]

[DOI]

CoRR, 2013

Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover.

[BibT_eX]

[DOI]

Sushant Sachdeva

Proceedings of the 28th Conference on Computational Complexity, 2013

The Approximability of the Binary Paintshop Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Stochastic Vehicle Routing with Recourse.

[BibT_eX]

[DOI]

Inge Li Gørtz

Viswanath Nagarajan

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Hardness of Finding Independent Sets in Almost q-Colorable Graphs.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

New and Improved Bounds for the Minimum Set Cover Problem.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On the hardness of learning intersections of two halfspaces.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs.

[BibT_eX]

[DOI]

Sushant Sachdeva

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Quasi-Random PCP and Hardness of 2-Catalog Segmentation.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Approximate Lasserre Integrality Gap for Unique Games.

[BibT_eX]

[DOI]

Preyas Popat

Proceedings of the Approximation, 2010

2009

SDP Integrality Gaps with Local ell_1-Embeddability.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

On hardness of learning intersection of two halfspaces.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Hardness of Minimizing and Learning DNF Expressions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2007

Hardness of Embedding Metric Spaces of Equal Size.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Frame packing algorithms for automotive applications.

[BibT_eX]

[DOI]

Nicolas Navet

J. Embed. Comput., 2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

A 3-Query Non-Adaptive PCP with Perfect Completeness.

[BibT_eX]

[DOI]