# Arnab Bhattacharyya

According to our database

Collaborative distances:

^{1}, Arnab Bhattacharyya authored at least 63 papers between 2006 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2020

Efficiently Learning and Sampling Interventional Distributions from Observations.

CoRR, 2020

Combinatorial Lower Bounds for 3-Query LDCs.

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

An Optimal Algorithm for ℓ

_{1}-Heavy Hitters in Insertion Streams and Related Problems.
ACM Trans. Algorithms, 2019

Average Bias and Polynomial Sources.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Parameterized Intractability of Even Set and Shortest Vector Problem.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Minimum Intervention Cover of a Causal Graph.

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.

ACM Trans. Algorithms, 2018

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Learning and Testing Causal Models with Interventions.

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Testing Sparsity over Known and Unknown Bases.

Proceedings of the 35th International Conference on Machine Learning, 2018

Improved Learning of k-Parities.

Proceedings of the Computing and Combinatorics - 24th International Conference, 2018

2017

Hardness of learning noisy halfspaces using polynomial thresholds.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Improved bounds for universal one-bit compressive sensing.

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

On the Gap between Outcomes of Voting Rules.

Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Lower Bounds for 2-Query LCCs over Large Alphabet.

Proceedings of the Approximation, 2017

2016

Lower bounds for 2-query LCCs over large alphabet.

Electronic Colloquium on Computational Complexity (ECCC), 2016

The Dictionary Testing Problem.

CoRR, 2016

Tight lower bounds for linear 2-query LCCs over finite fields.

Combinatorica, 2016

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems.

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

On Higher-Order Fourier Analysis over Non-Prime Fields.

Proceedings of the Approximation, 2016

2015

On the hardness of learning sparse parities.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Lower bounds for constant query affine-invariant LCCs and LTCs.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Fishing out Winners from Vote Streams.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Sample Complexity for Winner Prediction in Elections.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Using higher-order Fourier analysis over general fields.

Electronic Colloquium on Computational Complexity (ECCC), 2015

On learning k-parities with and without noise.

CoRR, 2015

Lower bounds for testing triangle-freeness in Boolean functions.

Computational Complexity, 2015

Algorithmic regularity for polynomials and applications.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

How friends and non-determinism affect opinion dynamics.

Proceedings of the 54th IEEE Conference on Decision and Control, 2015

2014

Polynomial decompositions in polynomial time.

Electronic Colloquium on Computational Complexity (ECCC), 2014

An explicit sparse recovery scheme in the L1-norm.

CoRR, 2014

Steiner transitive-closure spanners of low-dimensional posets.

Combinatorica, 2014

2013

Guest column: on testing affine-invariant properties over finite fields.

SIGACT News, 2013

Approximation algorithms for spanner problems and Directed Steiner Forest.

Inf. Comput., 2013

On testing affine-invariant properties.

Electronic Colloquium on Computational Complexity (ECCC), 2013

A Bipartite Graph with Non-Unimodal Independent Set Sequence.

Electr. J. Comb., 2013

On the convergence of the Hegselmann-Krause system.

Proceedings of the Innovations in Theoretical Computer Science, 2013

An Algebraic Characterization of Testable Boolean CSPs.

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.

SIAM J. Discrete Math., 2012

Transitive-Closure Spanners.

SIAM J. Comput., 2012

Testing Assignments of Boolean CSPs.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing Low Complexity Affine-Invariant Properties.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Every locally characterized affine-invariant property is testable.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing Permanent Oracles - Revisited.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing Odd-Cycle-Freeness in Boolean Functions.

Combinatorics, Probability & Computing, 2012

2011

Testability of linear-invariant properties.

PhD thesis, 2011

Testing Linear-Invariant Non-Linear Properties.

Theory of Computing, 2011

Tight lower bounds for 2-query LCCs over finite fields.

Electronic Colloquium on Computational Complexity (ECCC), 2011

The Complexity of Linear Dependence Problems in Vector Spaces.

Proceedings of the Innovations in Computer Science, 2011

Improved Approximation for the Directed Spanner Problem.

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

A Unified Framework for Testing Linear-Invariant Properties.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Separations of Matroid Freeness Properties.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Testing monotonicity of distributions over general partial orders.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Testing linear-invariant non-linear properties: A short report.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Improved Approximation for the Directed Spanner Problem

CoRR, 2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

CoRR, 2010

Optimal Testing of Reed-Muller Codes.

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Linear-Invariant Non-linear Properties: A Short Report.

Proceedings of the Property Testing - Current Research and Surveys, 2010

2009

Optimal testing of Reed-Muller codes.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Robust Regulatory Networks

CoRR, 2009

2008

A Note on the Distance to Monotonicity of Boolean Functions.

Electronic Colloquium on Computational Complexity (ECCC), 2008

2006

Morphogenesis as an amorphous computation.

Proceedings of the Third Conference on Computing Frontiers, 2006