Ragesh Jaiswal

Poojan 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

A Quantum Approximation Scheme for k-Means.

[BibT_eX]

[DOI]

CoRR, 2023

Clustering What Matters in Constrained Settings.

[BibT_eX]

[DOI]

CoRR, 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

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

[BibT_eX]

[DOI]

Inf. Process. Lett., 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

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

Faster Algorithms for the Constrained k-means Problem.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Sampling in Space Restricted Settings.

[BibT_eX]

[DOI]

Algorithmica, 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]

IACR Cryptol. ePrint Arch., 2016

2015

k-Means++ under approximation stability.

[BibT_eX]

[DOI]

Manu Agarwal

Arindam Pal

Theor. Comput. Sci., 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

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 Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems.

[BibT_eX]

[DOI]

Sandeep Sen

Algorithmica, 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

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

Analysis of k-Means++ for Separable Data.

[BibT_eX]

[DOI]

Nitin Garg

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

2010

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Bounded Independence Fools Halfspaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

2009

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

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

SIAM J. Comput., 2009

Chernoff-Type Direct Product Theorems.

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

J. Cryptol., 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]

Claire Monteleoni

Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2008

New proofs of (new) Direct Product Theorems.

[BibT_eX]

[DOI]

PhD thesis, 2008

2006

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.

[BibT_eX]

[DOI]

Russell Impagliazzo