N. V. Vinodchandran

Arnab Bhattacharyya

ACM Trans. Database Syst., September, 2023

Model Counting Meets Distinct Elements.

[BibT_eX]

[DOI]

Commun. ACM, September, 2023

Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu.

[BibT_eX]

[DOI]

SIAM J. Comput., June, 2023

Total Variation Distance Estimation Is as Easy as Probabilistic Inference.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma.

[BibT_eX]

[DOI]

CoRR, 2023

Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations.

[BibT_eX]

[DOI]

Michael Chen

A. Pavan

Proceedings of the 37th International Symposium on Distributed Computing, 2023

List and Certificate Complexities in Replicable Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

On Approximating Total Variation Distance.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Constraint Optimization over Semirings.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Model Counting Meets Distinct Elements in a Data Stream.

[BibT_eX]

[DOI]

SIGMOD Rec., 2022

The Geometry of Rounding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Pseudodeterminism: promises and lowerbounds.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size.

[BibT_eX]

[DOI]

Sourav Chakraborty

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

A Scalable t-wise Coverage Estimator.

[BibT_eX]

[DOI]

Proceedings of the 44th IEEE/ACM 44th International Conference on Software Engineering, 2022

Distinct Elements in Streams: An Algorithm for the (Text) Book.

[BibT_eX]

[DOI]

Sourav Chakraborty

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Efficient interventional distribution learning in the PAC framework.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Promise Problems Meet Pseudodeterminism.

[BibT_eX]

[DOI]

Peter Dixon

Electron. Colloquium Comput. Complex., 2021

Efficient inference of interventional distributions.

[BibT_eX]

[DOI]

CoRR, 2021

Model Counting meets F0 Estimation.

[BibT_eX]

[DOI]

CoRR, 2021

Near-optimal learning of tree-structured distributions by Chow-Liu.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Model Counting meets F0 Estimation.

[BibT_eX]

[DOI]

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Estimating the Size of Union of Sets in Streaming Models.

[BibT_eX]

[DOI]

Sourav Chakraborty

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Complete Problems for Multi-Pseudodeterministic Computations.

[BibT_eX]

[DOI]

Peter Dixon

A. Pavan

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Testing Product Distributions: A Closer Look.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2021

2020

Perfect Zero Knowledge: New Upperbounds and Relativized Separations.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2020

Efficiently Learning and Sampling Interventional Distributions from Observations.

[BibT_eX]

[DOI]

CoRR, 2020

Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning and Sampling of Atomic Interventions from Observations.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory.

[BibT_eX]

[DOI]

Algorithmica, 2018

New Algorithms for Distributed Sliding Windows.

[BibT_eX]

[DOI]

Sutanu Gayen

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

On Pseudodeterministic Approximation Algorithms.

[BibT_eX]

[DOI]

Peter Dixon

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

KmerEstimate: A Streaming Algorithm for Estimating k-mer Counts with Optimal Space Usage.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM International Conference on Bioinformatics, 2018

2017

Fractal features for automatic detection of dysarthria.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE EMBS International Conference on Biomedical & Health Informatics, 2017

2016

Budgeted testing through an algorithmic lens.

[BibT_eX]

[DOI]

Myra B. Cohen

Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2016

Constrained Group Testing to Predict Binding Response of Candidate Compounds.

[BibT_eX]

[DOI]

Proceedings of the 2016 SIAM International Conference on Data Mining, 2016

A Note on the Advice Complexity of Multipass Randomized Logspace.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Algorithms for k-median Clustering over Distributed Streams.

[BibT_eX]

[DOI]

Sutanu Gayen

Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

Computing triangle and open-wedge heavy-hitters in large networks.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE International Conference on Big Data (IEEE BigData 2016), 2016

2015

On Optimal Language Compression for Sets in PSPACE/poly.

[BibT_eX]

[DOI]

Marius Zimand

Theory Comput. Syst., 2015

On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape.

[BibT_eX]

[DOI]

Debasis Mandal

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.

[BibT_eX]

[DOI]

Diptarka Chakraborty

Lin F. Yang

Electron. Colloquium Comput. Complex., 2014

ReachFewL = ReachUL.

[BibT_eX]

[DOI]

Comput. Complex., 2014

2013

An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Space complexity of perfect matching in bounded genus bipartite graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

On the power of unambiguity in log-space.

[BibT_eX]

[DOI]

Comput. Complex., 2012

2010

Green's Theorem and Isolation in Planar Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs.

[BibT_eX]

[DOI]

Derrick Stolee

Electron. Colloquium Comput. Complex., 2010

On the Power of Unambiguity in Logspace.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Resource-bounded Dimension in Computational Learning Theory

[BibT_eX]

[DOI]

CoRR, 2010

A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources.

[BibT_eX]

[DOI]

Derrick Stolee

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Directed Planar Reachability Is in Unambiguous Log-Space.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2009

A log-space algorithm for reachability in planar DAGs with few sources.

[BibT_eX]

[DOI]

Derrick Stolee

Electron. Colloquium Comput. Complex., 2009

Kolmogorov Complexity in Randomness Extraction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

An efficient and attack-resistant key agreement scheme for secure group communications in mobile ad-hoc networks.

[BibT_eX]

[DOI]

Wirel. Commun. Mob. Comput., 2008

Kernels for Generalized Multiple-Instance Learning.

[BibT_eX]

[DOI]

IEEE Trans. Pattern Anal. Mach. Intell., 2008

Relations between Average-Case and Worst-Case Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

Partial Bi-immunity, Scaled Dimension, and NP-Completeness.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

On reoptimizing multi-class classifiers.

[BibT_eX]

[DOI]

Mach. Learn., 2008

2-Local Random Reductions to 3-Valued Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2008

2007

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

2006

Computational depth: Concept and applications.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Dimension, entropy rates, and compression.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

A New Cryptographic Scheme for Securing Dynamic Conferences in Data Networks.

[BibT_eX]

[DOI]

Proceedings of IEEE International Conference on Communications, 2006

Some Results on Average-Case Hardness Within the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Rahul Santhanam

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

2005

A note on the circuit complexity of PP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Entropy rates and finite-state dimension.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Nondeterministic circuit minimization problem and derandomizing Arthur-Merlin games.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2005

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Derandomizing Arthur-Merlin Games using Hitting Sets.

[BibT_eX]

[DOI]

Peter Bro Miltersen

Comput. Complex., 2005

A balanced key tree approach for dynamic secure group communication.

[BibT_eX]

[DOI]

Proceedings of the 14th International Conference On Computer Communications and Networks, 2005

CRTDH: an efficient key agreement scheme for secure group communications in wireless ad hoc networks.

[BibT_eX]

[DOI]

Ravi K. Balachandran

Byrav Ramamurthy

Xukai Zou

Proceedings of IEEE International Conference on Communications, 2005

On computing disjoint paths with dependent cost structure in optical networks.

[BibT_eX]

[DOI]

Ajay Kumar Todimala

Byrav Ramamurthy

Proceedings of the 2nd International Conference on Broadband Networks (BROADNETS 2005), 2005

2004

Counting Complexity of Solvable Black-Box Group Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

AMexp[nsube](NP[cap]coNP)/poly.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

An Extended Kernel for Generalized Multiple-Instance Learning.

[BibT_eX]

[DOI]

Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), 2004

SVM-based generalized multiple-instance learning via approximate box counting.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning, 2004

Learning DNFs and Circuits Using Teaching Assistants.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

Partial Bi-immunity and NP-Completeness.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Using Depth to Capture Average-Case Complexity.

[BibT_eX]

[DOI]

Luis Antunes

Lance Fortnow

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

The Query Complexity of Program Checking by Constant-Depth Circuits.

[BibT_eX]

[DOI]

K. V. Subrahmanyam

Chic. J. Theor. Comput. Sci., 2002

2000

The counting complexity of group-definable languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Exact learning via teaching assistants.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

1999

Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.

[BibT_eX]

[DOI]

Peter Bro Miltersen

Osamu Watanabe

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1997

Solvable Black-Box Group Problems are Low for PP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Improved Lowness Results for Solvable Black-box Group Problems.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

Exact Learning via Teaching Assistants (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996

The Complexity of Exactly Learning Algebraic Concepts. (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995

A Note on Mod and Generalised Mod Classes.

[BibT_eX]

[DOI]

Meena Mahajan

Inf. Process. Lett., 1995

1994

A Note on SpanP Functions.

[BibT_eX]

[DOI]

Meena Mahajan

Thomas Thierauf