Aduri Pavan

CoRR, 2024

Total Variation Distance for Product Distributions is #P-Complete.

[BibT_eX]

[DOI]

CoRR, 2024

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints.

[BibT_eX]

[DOI]

Yanhui Zhu

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

Total Variation Distance Meets Probabilistic Inference.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Model Counting Meets F0 Estimation.

[BibT_eX]

[DOI]

N. Variyam Vinodchandran

Arnab Bhattacharyya

Kuldeep S. Meel

ACM Trans. Database Syst., September, 2023

Model Counting Meets Distinct Elements.

[BibT_eX]

[DOI]

Commun. ACM, September, 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

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

Maximizing submodular functions under submodular constraints.

[BibT_eX]

[DOI]

Madhavan R. Padmanabhan

Yanhui Zhu

Proceedings of the Uncertainty in Artificial Intelligence, 2023

Size-constrained k-submodular maximization in near-linear time.

[BibT_eX]

[DOI]

Christopher John Quinn

Proceedings of the Uncertainty in Artificial Intelligence, 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

2021

Measuring the impact of influence on individuals: roadmap to quantifying attitude.

[BibT_eX]

[DOI]

Xiaoyun Fu

Madhavan R. Padmanabhan

Soc. Netw. Anal. Min., 2021

Promise Problems Meet Pseudodeterminism.

[BibT_eX]

[DOI]

Peter Dixon

Electron. Colloquium Comput. Complex., 2021

Model Counting meets F0 Estimation.

[BibT_eX]

[DOI]

CoRR, 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

Complete Problems for Multi-Pseudodeterministic Computations.

[BibT_eX]

[DOI]

Peter Dixon

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

Multi-Objective Submodular Optimization with Approximate Oracles and Influence Maximization.

[BibT_eX]

[DOI]

Xiaoyun Fu

Rishabh Rajendra Bhatt

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

2020

Perfect Zero Knowledge: New Upperbounds and Relativized Separations.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2020

Disrupting Diffusion: Critical Nodes in Network.

[BibT_eX]

[DOI]

Proceedings of the IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2020

2019

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

On Pseudodeterministic Approximation Algorithms.

[BibT_eX]

[DOI]

Peter Dixon

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

Influence Maximization in Social Networks With Non-Target Constraints.

[BibT_eX]

[DOI]

Madhavan R. Padmanabhan

Naresh Somisetty

Neeraj Kavassery-Parakkat

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

Improved Triangle Counting in Graph Streams: Power of Multi-Sampling.

[BibT_eX]

[DOI]

Kiana Mousavi Hanjani

Proceedings of the IEEE/ACM 2018 International Conference on Advances in Social Networks Analysis and Mining, 2018

2016

A thirty Year old conjecture about promise problems.

[BibT_eX]

[DOI]

Comput. Complex., 2016

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.

[BibT_eX]

[DOI]

Algorithmica, 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

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

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

On the NP-Completeness of the Minimum Circuit Size Problem.

[BibT_eX]

[DOI]

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis.

[BibT_eX]

[DOI]

Debasis Mandal

Rajeswari Venugopalan

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

Raghunath Tewari

N. Variyam Vinodchandran

Lin F. Yang

Electron. Colloquium Comput. Complex., 2014

Strong Reductions and Isomorphism of Complete Sets.

[BibT_eX]

[DOI]

Ryan C. Harkins

Comput., 2014

2013

Counting and Sampling Triangles from a Graph Stream.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2013

Length-Increasing Reductions for PSPACE-Completeness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 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

Parallel triangle counting in massive streaming graphs.

[BibT_eX]

[DOI]

Kanat Tangwongsan

Srikanta Tirthapura

Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 2013

2012

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses.

[BibT_eX]

[DOI]

Xiaoyang Gu

Theory Comput. Syst., 2012

On the power of unambiguity in log-space.

[BibT_eX]

[DOI]

Raghunath Tewari

Comput. Complex., 2012

A Thirty Year Old Conjecture about Promise Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

The fault tolerance of NP-hard problems.

[BibT_eX]

[DOI]

Christian Glaßer

Stephen D. Travers

Inf. Comput., 2011

2010

On the Power of Unambiguity in Logspace.

[BibT_eX]

[DOI]

Raghunath Tewari

Electron. Colloquium Comput. Complex., 2010

2009

Kolmogorov Complexity in Randomness Extraction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

Splitting NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

Proving SAT does not have small circuits with an application to the two queries problem.

[BibT_eX]

[DOI]

Samik Sengupta

J. Comput. Syst. Sci., 2008

2-Local Random Reductions to 3-Valued Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Hardness Hypotheses, Derandomization, and Circuit Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 2008

2007

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Range-Efficient Counting of Distinct Elements in a Massive Data Stream.

[BibT_eX]

[DOI]

Srikanta Tirthapura

SIAM J. Comput., 2007

Autoreducibility, mitoticity, and immunity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

Robustness of PSPACE-complete sets.

[BibT_eX]

[DOI]

Fengming Wang

Inf. Process. Lett., 2007

2006

Properties of NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Comparing Reductions to NP-Complete Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Mitosis in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 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

Some Results on Derandomization.

[BibT_eX]

[DOI]

Harry Buhrman

Theory Comput. Syst., 2005

Resource-bounded strong dimension versus resource-bounded category.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Redundancy in Complete Sets

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Range Efficient Computation of F0 over Massive Data Streams.

[BibT_eX]

[DOI]

Srikanta Tirthapura

Proceedings of the 21st International Conference on Data Engineering, 2005

2004

On Higher Arthur-Merlin Classes.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Partial Bi-Immunity and NP-Completeness

[BibT_eX]

[DOI]

Pramodchandran N. Variyam

Electron. Colloquium Comput. Complex., 2004

Partial Bi-immunity and NP-Completeness.

[BibT_eX]

[DOI]

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

2003

Proving SAT does not have Small Circuits with an Application to the Two.

[BibT_eX]

[DOI]

Samik Sengupta

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Bi-Immunity Separates Strong NP-Completeness Notions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

2001

Separation of NP-Completeness Notions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

Distributionally Hard Languages.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2001

2000

Complete distributional problems, hard languages, and resource-bounded measure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

1999

Reductions Do Not Preserve Fast Convergence Rates in Average Time.

[BibT_eX]

[DOI]

Jay Belanger

Jie Wang

Algorithmica, 1999

On the Hardness of Permanent.

[BibT_eX]

[DOI]

Jin-yi Cai