Research | Arnab Bhattacharyya

Professional Activities

I organize an Algorithms and Complexity reading group at CSA. Our goal is to learn about recent works of interest in an informal setting. Feel free to drop by if you're in the Bangalore area, and send me an email if you want to give a talk! Below is our calendar.

Co-organizer of the Symposium on Learning, Algorithms and Complexity

Steering committee member for NMI Thematic Year on Complexity Theory and Cryptography (2016-17)

Program Committees: FSTTCS 2013, SODA 2016, KDD 2016, AAMAS 2017, RANDOM 2017, FSTTCS 2017

My CV for more information (updated October, 2016).

Publications, preprints, and surveys

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C.S, and Pasin Manurangsi. ICALP, 2018.

Hardness of learning noisy halfspaces using polynomial thresholds. Arnab Bhattacharyya, Suprovat Ghoshal, and Rishi Saket. COLT, 2018.

Testing sparsity over known and unknown bases. Siddharth Barman, Arnab Bhattacharyya, and Suprovat Ghoshal. ICML, 2018.

On learning k-parities with and without noise. Arnab Bhattacharyya, Ameet Gadekar and Ninad Rajgopal. COCOON, 2018.

Machine learning and Statistical Analysis for Materals Science: Stability and Transferability of Fingerprint Descriptors and Chemical Insights. Praveen Pankajakshan, Suchismita Sanyal, Onno E. de Noord, Indranil Bhattacharya, Arnab Bhattacharyya, and Umesh Waghmare. Chemistry of Materials, 2017.

Improved bounds for Universal One-Bit Compressive Sensing. Jayadev Acharya, Arnab Bhattacharyya, and Pritish Kamath. ISIT, 2017.

Lower bounds for 2-query LCCs over large alphabet. Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal. RANDOM, 2017.

An optimal algorithm for heavy hitters in insertion streams and related problems. Arnab Bhattacharyya, Palash Dey, and David Woodruff. PODS, 2016. [Note: subsumes a previous preprint.]

On the hardness of learning sparse parities. Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. ESA, 2016.

Lower bounds for constant query affine-invariant LCCs and LTCs. Arnab Bhattacharyya and Sivakanth Gopi. CCC, 2016.

Higher-order Fourier analysis over non-prime fields. Arnab Bhattacharyya, Chetan Gupta , and Abhishek Bhowmick. RANDOM, 2016. [Earlier version available here]

How friends and non-determinism affect opinion dynamics. Arnab Bhattacharyya and Kirankumar Shiragur. CDC, 2015.

Sample Complexity for Winner Prediction in Elections. Arnab Bhattacharyya and Palash Dey. AAMAS, 2015.

An explicit sparse recovery scheme in the L1-norm. Arnab Bhattacharyya and Vineet Nair. 2014.

Polynomial decompositions in polynomial time. Arnab Bhattacharyya. ESA, 2014.

On testing affine-invariant properties. Arnab Bhattacharyya. Guest survey column on ACM SIGACT News, vol. 44, no. 4, 2013.

Algorithmic Regularity for polynomials and applications. Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani. SODA, 2015.

A bipartite graph with non-unimodal independent set sequence. Arnab Bhattacharyya and Jeff Kahn. Electronic Journal of Combinatorics, vol. 20, no. 4, 2013.

Every locally characterized affine-invariant property is testable. Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. STOC, 2013.

On the convergence of the Hegselmann-Krause System. Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, and Huy L. Nguyen. ITCS, 2013.

An Algebraic Characterization of Testable CSPs. Arnab Bhattacharyya and Yuichi Yoshida. ICALP, 2013.

Testing Permanent Oracles -- Revisited. Sanjeev Arora, Arnab Bhattacharyya, Sushant Sachdeva, and Rajsekar Manokaran. RANDOM, 2012.

Testing Low Complexity Affine-Invariant Properties. Arnab Bhattacharyya, Eldar Fischer, and Shachar Lovett. SODA, 2013.

Testing Odd-Cycle-Freeness in Boolean Functions. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, and Asaf Shapira. SODA, 2012. Combinatorics, Probability & Computing, vol. 21, no. 6, 2012.

Tight lower bounds for 2-query LCCs over finite fields. Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, and Amir Shpilka. FOCS, 2011. Combinatorica (to appear).

Improved Approximation for the Directed Spanner Problem. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. ICALP, 2011. Special issue of Information and Computation, vol. 222, 2013.

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. Combinatorica (to appear).

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, , and Asaf Shapira. FOCS, 2010. Random Structures & Algorithms (to appear).

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. SIAM Journal of Discrete Math, vol. 26, no. 2, 2012.

Lower Bounds for Testing Triangle Freeness in Boolean Functions. Arnab Bhattacharyya and Ning Xie. SODA, 2010.

Testing Linear-Invariant Non-Linear Properties. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. STACS, 2009. Theory of Computing, vol. 7, no. 1, 2011.

Transitive Closure Spanners. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David Woodruff. SODA, 2009. SIAM Journal of Computing, vol. 41, no. 6, 2012.

A note on the distance to monotonicity of Boolean functions. Arnab Bhattacharyya. 2006.

Morphogenesis as an amorphous computation. Arnab Bhattacharyya. 2006.

Implementing Probabilistically Checkable Proofs of Proximity. Arnab Bhattacharyya. CSAIL Technical Report, 2005.