A fast algorithm for well-spaced points and approximate delaunay graphs. - Gary L. Miller; Donald R. Sheehy; Ameya Velingker (SoCG, 2013)

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. - Mahdi Cheraghchi; Venkatesan Guruswami; Ameya Velingker (SIAM J. Comput., 2013)

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. - Venkatesan Guruswami; Madhu Sudan 001; Ameya Velingker; Carol Wang (Electron. Colloquium Comput. Complex., 2014)

An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. - Venkatesan Guruswami; Ameya Velingker (Electron. Colloquium Comput. Complex., 2014)

Communication with Partial Noiseless Feedback. - Bernhard Haeupler; Pritish Kamath; Ameya Velingker (APPROX-RANDOM, 2015)

Approximating Nearest Neighbor Distances. - Michael B. Cohen; Brittany Terese Fasy; Gary L. Miller; Amir Nayyeri; Donald R. Sheehy; Ameya Velingker (WADS, 2015)

Constructing Ramanujan Graphs Using Shift Lifts. - Karthekeyan Chandrasekaran; Ameya Velingker (CoRR, 2015)

On the Sensitivity Conjecture for Read-k Formulas. - Mitali Bafna; Satyanarayana V. Lokam; Sébastien Tavenas; Ameya Velingker (Electron. Colloquium Comput. Complex., 2016)

Bridging the Capacity Gap Between Interactive and One-Way Communication. - Bernhard Haeupler; Ameya Velingker (Electron. Colloquium Comput. Complex., 2016)

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. - Venkatesan Guruswami; Ameya Velingker; Santhoshini Velusamy (APPROX-RANDOM, 2017)

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. - Haim Avron; Michael Kapralov; Cameron Musco; Christopher Musco; Ameya Velingker; Amir Zandieh (ICML, 2017)

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. - Michael Kapralov; Sanjeev Khanna; Madhu Sudan 001; Ameya Velingker (SODA, 2017)

Dimension-independent Sparse Fourier Transform. - Michael Kapralov; Ameya Velingker; Amir Zandieh (SODA, 2019)

A universal sampling method for reconstructing signals with simple Fourier transforms. - Haim Avron; Michael Kapralov; Cameron Musco; Christopher Musco; Ameya Velingker; Amir Zandieh (STOC, 2019)

Scalable and Differentially Private Distributed Aggregation in the Shuffled Model. - Badih Ghazi; Rasmus Pagh; Ameya Velingker (CoRR, 2019)

Private Heavy Hitters and Range Queries in the Shuffled Model. - Badih Ghazi; Noah Golowich; Ravi Kumar 001; Rasmus Pagh; Ameya Velingker (CoRR, 2019)

On the Power of Multiple Anonymous Messages. - Badih Ghazi; Noah Golowich; Ravi Kumar 001; Rasmus Pagh; Ameya Velingker (IACR Cryptol. ePrint Arch., 2019)

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing. - Amir Zandieh; Navid Nouri; Ameya Velingker; Michael Kapralov; Ilya P. Razenshteyn (AISTATS, 2020)

Private Aggregation from Fewer Anonymous Messages. - Badih Ghazi; Pasin Manurangsi; Rasmus Pagh; Ameya Velingker (EUROCRYPT (2), 2020)

Pure Differentially Private Summation from Anonymous Messages. - Badih Ghazi; Noah Golowich; Ravi Kumar 001; Pasin Manurangsi; Rasmus Pagh; Ameya Velingker (ITC, 2020)

Oblivious Sketching of High-Degree Polynomial Kernels. - Thomas D. Ahle; Michael Kapralov; Jakob Bæk Tejs Knudsen; Rasmus Pagh; Ameya Velingker; David P. Woodruff; Amir Zandieh (SODA, 2020)

On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. - Badih Ghazi; Noah Golowich; Ravi Kumar 001; Rasmus Pagh; Ameya Velingker (EUROCRYPT (3), 2021)

Linear Space Streaming Lower Bounds for Approximating CSPs. - Chi-Ning Chou; Alexander Golovnev; Madhu Sudan 001; Ameya Velingker; Santhoshini Velusamy (Electron. Colloquium Comput. Complex., 2021)

Private Robust Estimation by Stabilizing Convex Relaxations. - Pravesh Kothari; Pasin Manurangsi; Ameya Velingker (COLT, 2022)

Exphormer: Sparse Transformers for Graphs. - Hamed Shirzad; Ameya Velingker; Balaji Venkatachalam; Danica J. Sutherland; Ali Kemal Sinop (ICML, 2023)

Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. - Ameya Velingker; Maximilian Vötsch; David P. Woodruff; Samson Zhou (ICML, 2023)

Affinity-Aware Graph Networks. - Ameya Velingker; Ali Kemal Sinop; Ira Ktena; Petar Velickovic; Sreenivas Gollapudi (NeurIPS, 2023)

Locality-Aware Graph Rewiring in GNNs. - Federico Barbero; Ameya Velingker; Amin Saberi; Michael M. Bronstein; Francesco Di Giovanni (ICLR, 2024)

Weisfeiler-Leman at the margin: When more expressivity matters. - Billy Joe Franks; Christopher Morris 001; Ameya Velingker; Floris Geerts (ICML, 2024)

Even Sparser Graph Transformers. - Hamed Shirzad; Honghao Lin; Balaji Venkatachalam; Ameya Velingker; David P. Woodruff; Danica J. Sutherland (NeurIPS, 2024)

Efficient Location Sampling Algorithms for Road Networks. - Sara Ahmadian; Sreenivas Gollapudi; Kostas Kollias; Vivek Kumar; Ameya Velingker; Santhoshini Velusamy (WWW (Companion Volume), 2024)

A Theory for Compressibility of Graph Transformers for Transductive Learning. - Hamed Shirzad; Honghao Lin; Ameya Velingker; Balaji Venkatachalam; David P. Woodruff; Danica J. Sutherland (CoRR, 2024)