Publications

Billy J. Franks, Christopher Morris, Ameya Velingker, Floris Geerts (2024). Weisfeiler-Leman at the margin: When more expressivity matters. arXiv:2402.07568.

Cite arXiv

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

Cite arXiv

Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Veličković, Sreenivas Gollapudi (2023). Affinity-Aware Graph Networks. NeurIPS 2023.

Cite Video arXiv URL

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

Cite Code Video arXiv URL

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

Cite Video arXiv URL

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

Cite arXiv URL

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy (2022). Linear space streaming lower bounds for approximating CSPs. STOC 2022.

Cite Video arXiv ECCC URL

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

Cite Video arXiv IACR URL

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

Cite arXiv URL

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

Cite arXiv URL

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

Cite arXiv URL

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

Cite arXiv URL

Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh (2019). A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms. STOC 2019.

Cite arXiv URL

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

Cite arXiv URL

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

Cite URL

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

Cite arXiv URL

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

Cite URL

Bernhard Haeupler, Ameya Velingker (2017). Bridging the Capacity Gap Between Interactive and One-Way Communication. SODA 2017.

Cite arXiv ECCC URL

Karthekeyan Chandrasekaran, Ameya Velingker (2017). Constructing Ramanujan Graphs Using Shift Lifts. Linear Algebra and its Applications 529 (2017).

Cite arXiv URL

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

Cite ECCC URL

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

Cite URL

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

Cite arXiv URL

Venkatesan Guruswami, Ameya Velingker (2015). An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CCC 2015.

Cite Video arXiv ECCC URL

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang (2015). Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA 2015.

Cite ECCC URL

Gary L. Miller, Donald R. Sheehy, Ameya Velingker (2013). A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs. SoCG 2013.

Cite arXiv URL

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker (2013). Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SODA 2013. SIAM Journal on Computing 42(5).

Cite arXiv ECCC URL URL