Ameya Velingker

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