Amey Bhangale

According to our database, Amey Bhangale authored at least 44 papers between 2015 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

On approximability of Satisfiable k-CSPs: I.

Amey Bhangale, Subhash Khot, Dor Minzer

Comput. Complex., December, 2025

The Quest towards Optimal Approximability of CSPs.

Amey Bhangale

ACM SIGLOG News, January, 2025

On Approximability of Satisfiable k-CSPs: V.

Amey Bhangale, Subhash Khot, Dor Minzer

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Parallel Repetition for 3-Player XOR Games.

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Leader Election with Poly-Logarithmic Communication Per Party.

Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak, Sravya Yandamuri

Proceedings of the Advances in Cryptology - CRYPTO 2025, 2025

2024

Reasonable Bounds for Combinatorial Lines of Length Three.

Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VII.

Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable k-CSPs: VI.

Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

Electron. Colloquium Comput. Complex., 2024

On Approximability of Satisfiable <i>k</i>-CSPs: VII.

Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

CoRR, 2024

On Approximability of Satisfiable <i>k</i>-CSPs: VI.

Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

CoRR, 2024

On Approximability of Satisfiable k-CSPs: IV.

Amey Bhangale, Subhash Khot, Dor Minzer

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Parallel Repetition of k-Player Projection Games.

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Proceedings of the Approximation, 2024

2023

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$.

Amey Bhangale, Subhash Khot, Dor Minzer

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable <i>k</i>-CSPs: II.

Amey Bhangale, Subhash Khot, Dor Minzer

Electron. Colloquium Comput. Complex., 2023

On Approximability of Satisfiable <i>k</i>-CSPs: III.

Amey Bhangale, Subhash Khot, Dor Minzer

Electron. Colloquium Comput. Complex., 2023

Effective Bounds for Restricted 3-Arithmetic Progressions in F_pⁿ.

Amey Bhangale, Subhash Khot, Dor Minzer

CoRR, 2023

On Approximability of Satisfiable k-CSPs: III.

Amey Bhangale, Subhash Khot, Dor Minzer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On Approximability of Satisfiable k-CSPs: II.

Amey Bhangale, Subhash Khot, Dor Minzer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

A Toolbox for Barriers on Interactive Oracle Proofs.

Gal Arnon, Amey Bhangale, Alessandro Chiesa, Eylon Yogev

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

On approximability of satisfiable <i>k</i>-CSPs: I.

Amey Bhangale, Subhash Khot, Dor Minzer

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs.

Amey Bhangale, Aleksa Stankovic

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Mixing of 3-Term Progressions in Quasirandom Groups.

Amey Bhangale, Prahladh Harsha, Sourya Roy

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Efficient Adaptively-Secure Byzantine Agreement for Long Messages.

Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak

Proceedings of the Advances in Cryptology - ASIACRYPT 2022, 2022

2021

Optimal inapproximability of satisfiable k-LIN over non-abelian groups.

Amey Bhangale, Subhash Khot

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Rigid Matrices From Rectangular PCPs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

Improved Inapproximability of Rainbow Coloring.

Per Austrin, Amey Bhangale, Aditya Potukuchi

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut.

Amey Bhangale, Subhash Khot

Proceedings of the 35th Computational Complexity Conference, 2020

Hardness of Approximation of (Multi-)LCS over Small Alphabet.

Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar

Proceedings of the Approximation, 2020

2019

Simplified inpproximability of hypergraph coloring via t-agreeing families.

Per Austrin, Amey Bhangale, Aditya Potukuchi

Electron. Colloquium Comput. Complex., 2019

UG-Hardness to NP-Hardness by Losing Half.

Amey Bhangale, Subhash Khot

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Near-optimal approximation algorithm for simultaneous Max-Cut.

Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Note on the Joint Entropy of N/2-Wise Independence.

Amey Bhangale, Aditya Potukuchi

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors.

Amey Bhangale

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Bi-Covering: Covering Edges with Two Small Subsets of Vertices.

Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz

SIAM J. Discret. Math., 2017

A short note on the joint entropy of n/2-wise independence.

Amey Bhangale, Aditya Potukuchi

CoRR, 2017

Cube vs. Cube Low Degree Test.

Amey Bhangale, Irit Dinur, Inbal Livni Navon

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

An Improved Dictatorship Test with Perfect Completeness.

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Bicovering: Covering Edges With Two Small Subsets of Vertices.

Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On Fortification of General Games.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Electron. Colloquium Comput. Complex., 2015

The complexity of computing the minimum rank of a sign pattern matrix.

Amey Bhangale, Swastik Kopparty

CoRR, 2015

Simultaneous Approximation of Constraint Satisfaction Problems.

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

A Characterization of Hard-to-cover CSPs.

Amey Bhangale, Prahladh Harsha, Girish Varma

Proceedings of the 30th Conference on Computational Complexity, 2015

On Fortification of Projection Games.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Proceedings of the Approximation, 2015