Research | Arnab Bhattacharyya

Books

• Property Testing: Problems and Techniques. Arnab Bhattacharyya and Yuichi Yoshida. Springer, Singapore. 2022.

Publications, preprints, and surveys

• Distribution learning meets graph structure sampling. Arnab Bhattacharyya, Sutanu Gayen, Philips George John, Sayantan Sen, and N.V. Vinodchandran. 2024.

• Online bipartite matching with imperfect advice. Davin Choo, Themis Gouleakis, Chun Kai Ling, and Arnab Bhattacharyya. ICML, 2024.

• Total Variation Distance Estimation Is as Easy as Probabilistic Inference. Arnab Bhattacharyya, Sutanu Gayen, Kuldeep Meel, Dimitrios Myrisiotris, A. Pavan, and N.V. Vinodchandran. ICML, 2024.

• Optimal estimation of Gaussian (poly)trees. Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, and Arnab Bhattacharyya. AISTATS, 2024.

• On Approximating Total Variation Distance. Arnab Bhattacharyya, Sutanu Gayen, Kuldeep Meel, Dimitrios Myrisiotris, A. Pavan, and N.V. Vinodchandran. IJCAI, 2023.

• Active Structure Learning with Advice. Davin Choo, Themis Gouleakis, and Arnab Bhattacharyya. ICML, 2023.

• Near-Optimal Degree Testing for Bayes Nets . Vipul Arora, Arnab Bhattacharyya, Clément Canonne, and Joy Qiping Yang. ISIT, 2023.

• Sample complexity of distinguishing cause from effect. Jayadev Acharya, Sourbh Bhadane, Arnab Bhattacharyya, Saravanan Kandasamy, and Ziteng Sun. AISTATS, 2023.

• On the interventional Kullback-Leibler Divergence. Jonas Wildberger, Siyuan Guo, Arnab Bhattacharyya, Bernhard Schölkopf. CLeaR, 2023.

• Constraint optimization over semirings. A. Pavan ⓡ Kuldeep Meel ⓡ N.V. Vinodchandran ⓡ Arnab Bhattacharyya. AAAI, 2023.

• Low Degree Testing over the Reals. Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. SODA, 2023.

• Verification and search algorithms for causal DAGs. Davin Choo, Kirankumar Shiragur, and Arnab Bhattacharyya. NeurIPS, 2022.

• Independence Testing for Bounded Degree Bayesian Network. Arnab Bhattacharyya, Clément Canonne, and Joy Qiping Yang. NeurIPS, 2022.

• An Adaptive Kernel Approach to Federated Learning of Heterogeneous Causal Effects. Thanh Vinh Vo, Arnab Bhattacharyya, Young Lee, and Leong Tze-Yun. NeurIPS, 2022.

• Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals. Sidhant Bansal, Arnab Bhattacharyya, Anamay Chaturvedi, and Jonathan Scarlett. ISIT, 2022.

• Efficient interventional distribution learning in the PAC framework. Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Vedant Raval and N.V. Vinodchandran. AISTATS, 2022.

• Learning Sparse Fixed-Structure Gaussian Bayesian Networks. Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala, Sutanu Gayen, and Yuhao Wang. AISTATS, 2022.

• Identifiability of AMP chain graphs. Yuhao Wang and Arnab Bhattacharyya. AAAI, 2022.

• Testing Product Distributions: A Closer Look. Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, and N.V. Vinodchandran. ALT, 2021.

• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu. Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and N.V. Vinodchandran. STOC, 2021.

• Model Counting meets F0 Estimation. A. Pavan ⓡ N.V. Vinodchandran ⓡ Arnab Bhattacharyya ⓡ Kuldeep Meel. PODS, 2021. Received Best of PODS 2021, 2022 ACM SIGMOD Research Highlight and 2022 CACM Research Highlight awards. Invited to ACM Transactions on Database Systems, 2022.

• Efficient Statistics for Sparse Graphical Models from Truncated Samples. Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas. AISTATS, 2021.

• Efficiently Learning and Sampling Interventional Distributions from Observations. Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Ashwin Maran and N.V. Vinodchandran. ICML, 2020.

• Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning. Arnab Bhattacharyya, Sutanu Gayen, Kuldeep Meel, and N.V. Vinodchandran. NeurIPS, 2020.

• Combinatorial Lower Bounds for 3-query LDCs. Arnab Bhattacharyya, Sunil Chandran, and Suprovat Ghoshal. ITCS, 2020.

• Parameterized Intractability of Even Set and Shortest Vector Problem. Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx. Journal of the ACM, vol. 68, no. 3, 2021.

• A formal methods approach to predicting new features of the eukaryotic vesicle traffic system. Arnab Bhattacharyya, Ashutosh Gupta, Lakshmanan Kuppusamy, Somya Mani, Ankit Shukla, Mandayam Srivas, and Mukund Thattai. Acta Informatica, 2019.

• Minimum Intervention Cover of a Causal Graph. Saravanan Kandasamy, Arnab Bhattacharyya, and Vasant Honavar. AAAI, 2019.

• Machine Learning Constrained with Dimensional Analysis and Scaling Laws: Simple, Transferable, and Interpretable Models of Materials from Small Datasets. Narendra Kumar, Padmini Rajagopalan, Arnab Bhattacharyya, Praveen Pankajakshan, Suchismita Sanyal, Janakiraman Balachandran, and Umesh Waghmare. Chemistry of Materials, vol. 31, no. 2, 2019.

• Learning and Testing Causal Models with Interventions. Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. NeurIPS, 2018.

• 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, vol. 29, no. 10, 2017.

• Discovering vesicle traffic network constraints by model checking. Ankit Shukla, Arnab Bhattacharyya, Lakshmanan Kuppusamy, Mandayam Srivas, and Mukund Thattai. PLOS ONE, vol. 12, no. 7, 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. ACM Transactions on Algorithms, vol. 15, no. 1, 2019. [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. ACM Transactions on Computation Theory, vol. 9, no. 2, 2017.

• 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, vol. 36, 2016.
  

• 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, vol. 34, 2014.

• 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, vol. 46, no. 2, 2015.

• 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.