PI
Piotr Indyk
cs.DScs.LGcs.CGstat.MLcs.CCcs.ITmath.ITcs.IRcs.DBcs.DM
On Valency
published · living versionsW_84x4trpk·v1 · currentpublished
Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
with Justin Y. Chen, Ying Feng, Michael Kapralov, Ekaterina Kochetkova +1
1 version
W_gqr7y4r5·v1published
Preprints & journals
67 papers in the corpus · 2003–2026Compact Geometric Representations of Hierarchies2606.18520v1 · Prashant Gokhale, Piotr Indyk, Yuhao Liu et al.2026 · 0 citationsarXiv
Towards Tight Bounds for Streaming Attention2606.07205v1 · Justin Y. Chen, Ying Feng, Piotr Indyk et al.2026 · 0 citationsarXiv
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions2507.23539v1 · Piotr Indyk, Michael Kapralov, Kshiteej Sheth et al.2025 · 0 citationsarXiv
Even Faster Algorithm for the Chamfer Distance2505.08957v2 · Ying Feng, Piotr Indyk2025 · 1 citationarXiv
Graph-Based Algorithms for Diverse Similarity Search2502.13336v1 · Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy et al.2025 · 0 citationsarXiv
Optimal Algorithms for Augmented Testing of Discrete Distributions2412.00974v1 · Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld et al.2024 · 0 citationsarXiv
Statistical-Computational Trade-offs for Density Estimation2410.23087v1 · Anders Aamand, Alexandr Andoni, Justin Y. Chen et al.2024 · 0 citationsarXiv
SparseCL: Sparse Contrastive Learning for Contradiction Retrieval2406.10746v1 · Haike Xu, Zongyu Lin, Yizhou Sun et al.2024 · 0 citationsarXiv
A Bi-metric Framework for Fast Similarity Search2406.02891v1 · Haike Xu, Sandeep Silwal, Piotr Indyk2024 · 0 citationsarXiv
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors2312.13490v2 · Vaggos Chatziafratis, Piotr Indyk2023 · 0 citationsarXiv
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions2311.17868v1 · Justin Y. Chen, Piotr Indyk, David P. Woodruff2023 · 2 citationsarXiv
Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations2310.19126v1 · Piotr Indyk, Haike Xu2023 · 7 citationsarXiv
A Near-Linear Time Algorithm for the Chamfer Distance2307.03043v1 · Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram et al.2023 · 5 citationsarXiv
Data Structures for Density Estimation2306.11312v1 · Anders Aamand, Alexandr Andoni, Justin Y. Chen et al.2023 · 0 citationsarXiv
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees2304.07652v1 · Nicholas Schiefer, Justin Y. Chen, Piotr Indyk et al.2023 · 1 citationarXiv
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation2212.00642v1 · Ainesh Bakshi, Piotr Indyk, Praneeth Kacham et al.2022 · 0 citationsarXiv
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks2211.03232v2 · Anders Aamand, Justin Y. Chen, Piotr Indyk et al.2022 · 5 citationsarXiv
Faster Linear Algebra for Distance Matrices2210.15114v1 · Piotr Indyk, Sandeep Silwal2022 · 1 citationarXiv
Streaming Algorithms for Support-Aware Histograms2207.08686v1 · Justin Y. Chen, Piotr Indyk, Tal Wagner2022 · 0 citationsarXiv
Generalization Bounds for Data-Driven Numerical Linear Algebra2206.07886v1 · Peter Bartlett, Piotr Indyk, Tal Wagner2022 · 2 citationsarXiv
Triangle and Four Cycle Counting with Predictions in Graph Streams2203.09572v1 · Justin Y. Chen, Talya Eden, Piotr Indyk et al.2022 · 4 citationsarXiv
Targeted Supervised Contrastive Learning for Long-Tailed Recognition2111.13998v2 · Tianhong Li, Peng Cao, Yuan Yuan et al.2021 · 229 citationsarXiv
Embeddings and labeling schemes for A*2111.10041v1 · Talya Eden, Piotr Indyk, Haike Xu2021 · 0 citationsarXiv
Frequency Estimation with One-Sided Error2111.03953v1 · Piotr Indyk, Shyam Narayanan, David P. Woodruff2021 · 1 citationarXiv
(Optimal) Online Bipartite Matching with Degree Information2110.11439v3 · Anders Aamand, Justin Y. Chen, Piotr Indyk2021 · 0 citationsarXiv
Optimal (Euclidean) Metric Compression2110.03152v1 · Piotr Indyk, Tal Wagner2021 · 4 citationsarXiv
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering2107.01804v1 · Shyam Narayanan, Sandeep Silwal, Piotr Indyk et al.2021 · 1 citationarXiv
Learning-based Support Estimation in Sublinear Time2106.08396v1 · Talya Eden, Piotr Indyk, Shyam Narayanan et al.2021 · 11 citationsarXiv
Faster Kernel Matrix Algebra via Density Estimation2102.08341v2 · Arturs Backurs, Piotr Indyk, Cameron Musco et al.2021 · 0 citationsarXiv
Addressing Feature Suppression in Unsupervised Visual Representations2012.09962v5 · Tianhong Li, Lijie Fan, Yuan Yuan et al.2020 · 9 citationsarXiv
Online Page Migration with ML Advice2006.05028v1 · Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovi'c et al.2020 · 7 citationsarXiv
Estimating Entropy of Distributions in Constant Space1911.07976v1 · Jayadev Acharya, Sourbh Bhadane, Piotr Indyk et al.2019 · 3 citationsarXiv
Learning-Based Low-Rank Approximations1910.13984v1 · Piotr Indyk, Ali Vakilian, Yang Yuan2019 · 32 citationsarXiv
Scalable Nearest Neighbor Search for Optimal Transport1910.04126v4 · Arturs Backurs, Yihe Dong, Piotr Indyk et al.2019 · 21 citationsarXiv
(Learned) Frequency Estimation Algorithms under Zipfian Distribution1908.05198v2 · Anders Aamand, Piotr Indyk, Ali Vakilian2019 · 14 citationsarXiv
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm1907.03197v1 · Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan et al.2019 · 2 citationsarXiv
Sample-Optimal Low-Rank Approximation of Distance Matrices1906.00339v1 · Piotr Indyk, Ali Vakilian, Tal Wagner et al.2019 · 19 citationsarXiv
Scalable Fair Clustering1902.03519v2 · Arturs Backurs, Piotr Indyk, Krzysztof Onak et al.2019 · 101 citationsarXivon Valency
Set Cover in Sub-linear Time1902.03534v1 · Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld et al.2019 · 9 citationsarXiv
Learning Space Partitions for Nearest Neighbor Search1901.08544v4 · Yihe Dong, Piotr Indyk, Ilya Razenshteyn et al.2019 · 35 citationsarXiv
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners1807.11648v2 · Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan et al.2018 · 9 citationsarXiv
Approximate Nearest Neighbors in Limited Space1807.00112v1 · Piotr Indyk, Tal Wagner2018 · 7 citationsarXiv
Approximate Nearest Neighbor Search in High Dimensions1806.09823v1 · Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn2018 · 45 citationsarXiv
Practical Data-Dependent Metric Compression with Provable Guarantees1711.01520v1 · Piotr Indyk, Ilya Razenshteyn, Tal Wagner2017 · 2 citationsarXiv
Agile Millimeter Wave Networks with Provable Guarantees1706.06935v1 · Haitham Hassanieh, Omid Abari, Michael Rodreguez et al.2017 · 7 citationsarXiv
On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks1704.02958v1 · Arturs Backurs, Piotr Indyk, Ludwig Schmidt2017 · 17 citationsarXiv
Approximate Sparse Linear Regression1609.08739v2 · Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi2016 · 4 citationsarXiv
Near-Optimal (Euclidean) Metric Compression1609.06295v3 · Piotr Indyk, Tal Wagner2016 · 9 citationsarXiv
Simultaneous Nearest Neighbor Search1604.02188v1 · Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi et al.2016 · 0 citationsarXiv
Which Regular Expression Patterns are Hard to Match?1511.07070v2 · Arturs Backurs, Piotr Indyk2015 · 83 citationsarXiv
Career total: 411 works. 67 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.