Ameya Velingker

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 40

Top Topics

Kernel Ridge Regression

Nearest Neighbor

Polynomial Kernels

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Sara Ahmadian, Sreenivas Gollapudi, Kostas Kollias, Vivek Kumar, Ameya Velingker, Santhoshini Velusamy
Efficient Location Sampling Algorithms for Road Networks. WWW (Companion Volume) (2024)
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, Francesco Di Giovanni
Locality-Aware Graph Rewiring in GNNs. ICLR (2024)
Billy J. Franks, Christopher Morris, Ameya Velingker, Floris Geerts
Weisfeiler-Leman at the margin: When more expressivity matters. CoRR (2024)
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, Francesco Di Giovanni
Locality-Aware Graph-Rewiring in GNNs. CoRR (2023)
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR (2023)
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop
Exphormer: Sparse Transformers for Graphs. ICML (2023)
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML (2023)
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop
Exphormer: Sparse Transformers for Graphs. CoRR (2023)
Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Velickovic, Sreenivas Gollapudi
Affinity-Aware Graph Networks. NeurIPS (2023)
Pravesh Kothari, Pasin Manurangsi, Ameya Velingker
Private Robust Estimation by Stabilizing Convex Relaxations. COLT (2022)
Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Velickovic, Sreenivas Gollapudi
Affinity-Aware Graph Networks. CoRR (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear space streaming lower bounds for approximating CSPs. STOC (2022)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker
On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. EUROCRYPT (3) (2021)
Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker
Private Robust Estimation by Stabilizing Convex Relaxations. CoRR (2021)
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR (2021)
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Pure Differentially Private Summation from Anonymous Messages. CoRR (2020)
Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh
Oblivious Sketching of High-Degree Polynomial Kernels. SODA (2020)
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Pure Differentially Private Summation from Anonymous Messages. ITC (2020)
Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, Ilya P. Razenshteyn
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing. AISTATS (2020)
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Private Aggregation from Fewer Anonymous Messages. EUROCRYPT (2) (2020)
Michael Kapralov, Navid Nouri, Ilya P. Razenshteyn, Ameya Velingker, Amir Zandieh
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing. CoRR (2020)
Michael Kapralov, Ameya Velingker, Amir Zandieh
Dimension-independent Sparse Fourier Transform. CoRR (2019)
Michael Kapralov, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh
Oblivious Sketching of High-Degree Polynomial Kernels. CoRR (2019)
Badih Ghazi, Rasmus Pagh, Ameya Velingker
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model. CoRR (2019)
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
Private Aggregation from Fewer Anonymous Messages. CoRR (2019)
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker
Private Heavy Hitters and Range Queries in the Shuffled Model. CoRR (2019)
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
A universal sampling method for reconstructing signals with simple Fourier transforms. STOC (2019)
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker
On the Power of Multiple Anonymous Messages. IACR Cryptol. ePrint Arch. 2019 (2019)
Michael Kapralov, Ameya Velingker, Amir Zandieh
Dimension-independent Sparse Fourier Transform. SODA (2019)
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms. CoRR (2018)
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. CoRR (2018)
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. ICML (2017)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA (2017)
Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. APPROX-RANDOM (2017)
Bernhard Haeupler, Ameya Velingker
Bridging the Capacity Gap Between Interactive and One-Way Communication. SODA (2017)
Bernhard Haeupler, Ameya Velingker
Bridging the Capacity Gap Between Interactive and One-Way Communication. CoRR (2016)
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker
On the Sensitivity Conjecture for Read-k Formulas. Electron. Colloquium Comput. Complex. 23 (2016)
Bernhard Haeupler, Ameya Velingker
Bridging the Capacity Gap Between Interactive and One-Way Communication. Electron. Colloquium Comput. Complex. 23 (2016)
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker
On the Sensitivity Conjecture for Read-k Formulas. MFCS (2016)
Venkatesan Guruswami, Ameya Velingker
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Computational Complexity Conference (2015)
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker
Approximating Nearest Neighbor Distances. CoRR (2015)
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA (2015)
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, Ameya Velingker
Approximating Nearest Neighbor Distances. WADS (2015)
Karthekeyan Chandrasekaran, Ameya Velingker
Constructing Ramanujan Graphs Using Shift Lifts. CoRR (2015)
Bernhard Haeupler, Pritish Kamath, Ameya Velingker
Communication with Partial Noiseless Feedback. APPROX-RANDOM (2015)
Venkatesan Guruswami, Ameya Velingker
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CoRR (2014)
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. 21 (2014)
Venkatesan Guruswami, Ameya Velingker
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Electron. Colloquium Comput. Complex. 21 (2014)
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SIAM J. Comput. 42 (5) (2013)
Gary L. Miller, Donald R. Sheehy, Ameya Velingker
A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs CoRR (2013)
Gary L. Miller, Donald R. Sheehy, Ameya Velingker
A fast algorithm for well-spaced points and approximate delaunay graphs. SoCG (2013)
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SODA (2013)
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes CoRR (2012)
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. 19 (2012)