Amey Bhangale

Assistant professor at the CSE Department at University of California, Riverside.

Office: WCH 312

E-mail: <firstname>DOT<lastname> AT ucr DOT edu

---------------------------------------------------------------------

Prior to this, I spent a semester as a research fellow at the Simons Institute.

I was a post-doctoral fellow at Weizmann Institute of Science hosted by Irit Dinur.

I graduated from Rutgers University in 2017, where I was fortunate to be advised by Swastik Kopparty.

Research Interests : Approximation algorithms, Probabilistically Checkable Proofs, Hardness of approximation, Analysis of Boolean functions.

Papers

Reasonable Bounds for Combinatorial Lines of Length Three [arXiv]
- with Subhash Khot, Yang P. Liu, Dor Minzer
- (manuscript)
On Approximability of Satisfiable k-CSPs: VII [arXiv]
- with Subhash Khot, Yang P. Liu, Dor Minzer
- (manuscript)
On Approximability of Satisfiable k-CSPs: VI [arXiv]
- with Subhash Khot, Yang P. Liu, Dor Minzer
- (manuscript)
On Approximability of Satisfiable k-CSPs: V [eccc]
- with Subhash Khot, Dor Minzer
- STOC 25
Parallel Repetition for 3-XOR Games [arXiv]
- with Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
- STOC 25
Parallel Repetition of k-Player Projection Games [eccc]
- with Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
- RANDOM 24
Effective Bounds for Restricted 3-Arithmetic Progressions in F_p^n [eccc]
- with Subhash Khot, Dor Minzer
- (to appear in Discrete Analysis)
On Approximability of Satisfiable k-CSPs: IV [eccc]
- with Subhash Khot, Dor Minzer
- STOC 24
On Approximability of Satisfiable k-CSPs: III [eccc]
- with Subhash Khot, Dor Minzer
- STOC 23
On Approximability of Satisfiable k-CSPs: II [eccc]
- with Subhash Khot, Dor Minzer
- STOC 23
Efficient Adaptively-Secure Byzantine Agreement for Long Messages [ePrint]
- with Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak
- Asiacrypt 22
A Toolbox for Barriers on Interactive Oracle Proofs [ePrint]
- with Gal Arnon, Alessandro Chiesa, and Eylon Yogev
- TCC 22
On Approximability of Satisfiable k-CSPs: I [eccc]
- with Subhash Khot, Dor Minzer
- STOC 22
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. [arxiv]
- with Aleksa Stanković.
- ITCS 22
Mixing of 3-term progressions in Quasirandom Groups. [eccc]
- with Prahladh Harsha, and Sourya Roy.
- ITCS 22
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. [eccc]
- with Subhash Khot
- STOC 21
Rigid Matrices From Rectangular PCPs. [eccc]
- with Prahladh Harsha, Orr Paradise and Avishay Tal
- FOCS 20
Hardness of Approximation of (Multi-)LCS over Small Alphabet. [arxiv]
- with Diptarka Chakraborty and Rajendra Kumar
- APPROX 20
Simultaneous Max-Cut is harder to approximate than Max-Cut. [eccc]
- with Subhash Khot
- CCC 20
Simplified inapproximability of hypergraph coloring via t-agreeing families. [eccc]
- with Per Austrin and Aditya Potukuchi
- (manuscript)
Improved Inapproximability of Rainbow Coloring. [arxiv]
- with Per Austrin and Aditya Potukuchi
- SODA 20
UG-hardness to NP-hardness by Losing Half. [eccc]
- with Subhash Khot
- CCC 19
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. [eccc]
- ICALP 18
A short note on the joint entropy of n/2-wise independence. [arxiv]
- with Aditya Potukuchi
- ISIT 18
Near-optimal approximation algorithm for simultaneous Max-Cut. [arxiv]
- with Subhash Khot, Swastik Kopparty, Sushant Sachdeva and Devanathan Thiruvenkatachari
- SODA 18
An Improved Dictatorship Test with Perfect Completeness. [eccc]
- with Subhash Khot and Devanathan Thiruvenkatachari
- FSTTCS 17
Cube vs Cube Low Degree Test. [eccc]
- with Irit Dinur and Inbal Livni Navon
- ITCS 17
Bicovering: Covering edges with two small subsets of vertices. [eccc]
- with R. Gandhi, M. T. Hajiaghayi, R.Khandekar and G. Kortsarz
- ICALP 16
On Fortification of Projection Games. [eccc]
- with Ramprasad Saptharishi, Girish Varma and Rakesh Venkat
- RANDOM 15
A Characterization of hard-to-cover CSPs. [arxiv]
- with Prahladh Harsha and Girish Varma
- CCC 15
Simultaneous approximation of constraint satisfaction problems. [arxiv]
- with Swastik Kopparty and Sushant Sachdeva
- ICALP 15
The complexity of computing the minimum rank of a sign pattern matrix. [arxiv]
- with Swastik Kopparty

Teaching

Winter 25 - CS219 - Advanced Algorithms
Spring 24 - CS 141 - Intermediate Data Structures and Algorithms
Fall 23 - CS218 - Design and Analysis of Algorithms
Spring 23 - CS219 - Advanced Algorithms
Spring 23 - CS 141 - Intermediate Data Structures and Algorithms
Winter 23- CS 215 - Theory of Computations
Spring 22 - CS 141 - Intermediate Data Structures and Algorithms
Winter 22 - CS218 - Design and Analysis of Algorithms
Fall 21 - CS010C - Introduction to Data Structures and Algorithms
Spring 21 - CS 141 - Intermediate Data Structures and Algorithms
Winter 21 - CS 215 - Theory of Computations
Fall 20 - CS218 - Design and Analysis of Algorithms
Spring 20 - CS260 - Seminar course on Approximation algorithms
Spring 19 - Hardness of Approximation (with Irit Dinur)

Contact

446 N Campus Dr

Department of Computer Science and Engineering

University of California, Riverside

Riverside, CA 92521

WCH 312

E-mail: <firstname>DOT<lastname> AT ucr DOT edu

Papers

Teaching

Other links

CS Theory Reading Group (@UCR)

Contact