Amey Bhangale

According to our database, Amey Bhangale authored at least 36 papers between 2014 and 2024.

Collaborative distances:

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

2024

Rigid Matrices from Rectangular PCPs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

SIAM J. Comput., 2024

On Approximability of Satisfiable k-CSPs: V.

Amey Bhangale, Subhash Khot, Dor Minzer

Electron. Colloquium Comput. Complex., 2024

Parallel Repetition for 3-Player XOR Games.

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

CoRR, 2024

2023

Max-3-Lin Over Non-abelian Groups with Universal Factor Graphs.

Amey Bhangale, Aleksa Stankovic

Algorithmica, September, 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 k-CSPs: IV.

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

Parallel Repetition of k-Player Projection Games.

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, 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

IACR Cryptol. ePrint Arch., 2022

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

Amey Bhangale, Subhash Khot, Dor Minzer

Electron. Colloquium Comput. Complex., 2022

2021

Efficient Adaptively-Secure Byzantine Agreement for Long Messages.

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

IACR Cryptol. ePrint Arch., 2021

Mixing of 3-term progressions in Quasirandom Groups.

Amey Bhangale, Prahladh Harsha, Sourya Roy

Electron. Colloquium Comput. Complex., 2021

2020

A Characterization of Hard-to-Cover CSPs.

Amey Bhangale, Prahladh Harsha, Girish Varma

Theory Comput., 2020

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.

Amey Bhangale, Subhash Khot

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

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

Amey Bhangale, Diptarka Chakraborty, Rajendra Kumar

Proceedings of the Approximation, 2020

2019

Simultaneous Max-Cut is harder to approximate than Max-Cut.

Amey Bhangale, Subhash Khot

Electron. Colloquium Comput. Complex., 2019

UG-hardness to NP-hardness by Losing Half.

Amey Bhangale, Subhash Khot

Electron. Colloquium Comput. Complex., 2019

Simplified inpproximability of hypergraph coloring via t-agreeing families.

Per Austrin, Amey Bhangale, Aditya Potukuchi

Electron. Colloquium Comput. Complex., 2019

2018

NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors.

Amey Bhangale

Electron. Colloquium Comput. Complex., 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

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

An Improved Dictatorship Test with Perfect Completeness.

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

Electron. Colloquium Comput. Complex., 2017

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

Amey Bhangale, Aditya Potukuchi

CoRR, 2017

2016

Bicovering: Covering edges with two small subsets of vertices.

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

Electron. Colloquium Comput. Complex., 2016

Cube vs. Cube Low Degree Test.

Amey Bhangale, Irit Dinur, Inbal Livni Navon

Electron. Colloquium Comput. Complex., 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

On Fortification of Projection Games.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Proceedings of the Approximation, 2015

2014

Simultaneous Approximation of Constraint Satisfaction Problems.

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2014