Publications:
- Testing Low Complexity Affine-Invariant Properties. Arnab Bhattacharyya, Eldar Fischer, and Shachar Lovett. Submitted, 2012.
- Testing Odd-Cycle-Freeness in Boolean Functions. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, and Asaf Shapira. SODA, 2012.
- Tight lower bounds for 2-query LCCs over finite fields. Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, and Amir Shpilka. FOCS, 2011.
- Improved Approximation for the Directed Spanner Problem. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. ICALP, 2011. Invited to special issue of Information and Computation. (Preliminary versions here and here)
- Linear Programming and Combinatorial Bounds on Steiner Transitive-Closure Spanners. Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, and Grigory Yaroslavtsev. ICALP, 2011.
- The Complexity of Linear Dependence Problems in Vector Spaces. Arnab Bhattacharyya, Piotr Indyk, David Woodruff, and Ning Xie. ICS, 2011.
- Testing monotonicity of distributions over general partial orders. Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. ICS, 2011.
- A Unified Framework for Testing Linear-Invariant Properties. Arnab Bhattacharyya, Elena Grigorescu, and Asaf Shapira. FOCS, 2010. (Slides)
- Optimal testing of Reed-Muller codes. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. FOCS, 2010.
- Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, and David Woodruff. RANDOM, 2010. (Slides, Preliminary full version, An earlier version: ECCC TR09-046)
- Lower Bounds for Testing Triangle Freeness in Boolean Functions. Arnab Bhattacharyya and Ning Xie. SODA, 2010.
- Robust Regulatory Networks. Arnab Bhattacharyya and Bernhard Haeupler. Submitted, 2009.
- Testing Linear-Invariant Non-Linear Properties. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. STACS, 2009. (Slides, A short report, July 2010)
- Transitive Closure Spanners. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David Woodruff. SODA, 2009. (Slides)
- A short proof of the query complexity for monotonicity testing of boolean functions. Arnab Bhattacharyya. Manuscript, 2006.
- Morphogenesis as an Amorphous Computation. Accepted at ACM 2006 International Conference on Computing Frontiers. Arnab Bhattacharyya. Abstract
- Implementing Probabilistically Checkable Proofs of Proximity. Arnab Bhattacharyya. CSAIL Technical Report TR-2005-051.
I occasionally write expository notes mainly to facilitate my own understanding. I put them here in case somebody else finds them useful. Note that some of these are in an unfinished state.
- An analysis of a spectral-partitioning-type theorem from this paper
- A useful theorem about random walks from this paper
- An exposition of Mihail's combinatorial analysis of graph expansion
- Tolerant testers for self-correctable properties
My CV as of November 2011.