Ragesh Jaiswal

Algorithmica, August, 2025

A New Rejection Sampling Approach to k-means++ With Improved Trade-Offs.

[BibT_eX]

[DOI]

Poojan Chetan Shah

Shashwat Agrawal

CoRR, February, 2025

Quantum (Inspired) D2-sampling with Applications.

[BibT_eX]

[DOI]

Poojan Chetan Shah

Proceedings of the Thirteenth International Conference on Learning Representations, 2025

Robust-Sorting and Applications to Ulam-Median.

[BibT_eX]

[DOI]

Jatin Yadav

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Quantum (Inspired) D2-sampling with Applications.

[BibT_eX]

[DOI]

Poojan Chetan Shah

CoRR, 2024

FPT Approximation for Capacitated Sum of Radii.

[BibT_eX]

[DOI]

Jatin Yadav

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Universal Weak Coreset.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Tight FPT Approximation for Socially Fair Clustering.

[BibT_eX]

[DOI]

Inf. Process. Lett., August, 2023

Tight FPT approximation for constrained k-center and k-supplier.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2023

Clustering What Matters in Constrained Settings: Improved Outlier to Outlier-Free Reductions.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

On the k-means/median cost function.

[BibT_eX]

[DOI]

Yoav Freund

Inf. Process. Lett., 2022

2021

Tight FPT Approximation for Constrained k-Center and k-Supplier.

[BibT_eX]

[DOI]

CoRR, 2021

FPT Approximation for Socially Fair Clustering.

[BibT_eX]

[DOI]

CoRR, 2021

Hardness of Approximation for Euclidean k-Median.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Multiplicative Rank-1 Approximation using Length-Squared Sampling.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

FPT Approximation for Constrained Metric k-Median/Means.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

On Sampling Based Algorithms for k-Means.

[BibT_eX]

[DOI]

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

2019

A note on the relation between XOR and Selective XOR Lemmas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Streaming PTAS for Binary 𝓁0-Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2019

Streaming PTAS for Constrained k-Means.

[BibT_eX]

[DOI]

CoRR, 2019

2018

Approximate Correlation Clustering Using Same-Cluster Queries.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Approximate Clustering with Same-Cluster Queries.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Approximate Clustering.

[BibT_eX]

Sandeep Sen

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

On the k-Means/Median Cost Function.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Tight lower bound instances for k-means++ in two dimensions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Simultaneous Secrecy and Reliability Amplification for a General Channel Model.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Faster Algorithms for the Constrained k-Means Problem.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

2015

Improved analysis of D2-sampling based PTAS for k-means and other clustering problems.

[BibT_eX]

[DOI]

Mehul Kumar

Pulkit Yadav

Inf. Process. Lett., 2015

Noise Stable Halfspaces are Close to Very Small Juntas.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2015

Sampling in Space Restricted Settings.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Improved analysis of D2-sampling based PTAS for k-means and other Clustering problems.

[BibT_eX]

[DOI]

Mehul Kumar

Pulkit Yadav

CoRR, 2014

On Uniform Reductions between Direct Product and XOR Lemmas.

[BibT_eX]

[DOI]

CoRR, 2014

A Tight Lower Bound Instance for k-means++ in Constant Dimension.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2014

2013

A bad 2-dimensional instance for k-means++.

[BibT_eX]

[DOI]

Prachi Jain

Saumya Yadav

CoRR, 2013

k-means++ under Approximation Stability.

[BibT_eX]

[DOI]

Manu Agarwal

Arindam Pal

Proceedings of the Theory and Applications of Models of Computation, 2013

2012

On the Distribution of the Fourier Spectrum of Halfspaces

[BibT_eX]

[DOI]

CoRR, 2012

Congestion lower bounds for secure in-network aggregation.

[BibT_eX]

[DOI]

Raghav Bhaskar

Sidharth Telang

Proceedings of the Fifth ACM Conference on Security and Privacy in Wireless and Mobile Networks, 2012

A Simple D 2-Sampling Based PTAS for k-Means and other Clustering Problems.

[BibT_eX]

[DOI]

Sandeep Sen

Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

Analysis of k-Means++ for Separable Data.

[BibT_eX]

[DOI]

Nitin Garg

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

2009

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification.

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

SIAM J. Comput., 2009

Security Amplification for InteractiveCryptographic Primitives.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Streaming k-means approximation.

[BibT_eX]

[DOI]