Theory

Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility AAAI 2021 Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis AAAI 2021 Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging CVPR 2021 Square Root Bundle Adjustment for Large-Scale Reconstruction CVPR 2021 The Complexity Landscape of Claim-Augmented Argumentation Frameworks AAAI 2021 Training Neural Networks is ER-complete NeurIPS 2021 Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard AAAI 2021 All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation NeurIPS 2020 Augmenting the Power of (Partial) MaxSat Resolution with Extension AAAI 2020 A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search AAAI 2020 Convergence of Opinion Diffusion is PSPACE-Complete AAAI 2020 Hard Examples for Common Variable Decision Heuristics AAAI 2020 How the Duration of the Learning Period Affects the Performance of Random Gradient Selection Hyper-Heuristics AAAI 2020 Model Interpretability through the lens of Computational Complexity NeurIPS 2020 Randomized tests for high-dimensional regression: A more efficient and powerful solution NeurIPS 2020 Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing NeurIPS 2020 An Improved Quasi-Polynomial Algorithm for Approximate Well-Supported Nash Equilibria AAAI 2019 Computational Separations between Sampling and Optimization NeurIPS 2019 Estimating Entropy of Distributions in Constant Space NeurIPS 2019 Implementation of a Chomsky-Schützenberger n-best parser for weighted multiple context-free grammars NAACL 2019 Oblivious and Semi-Oblivious Boundedness for Existential Rules IJCAI 2019 On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles IJCAI 2019 On the Hardness of Probabilistic Inference Relaxations AAAI 2019 Ontology Approximation in Horn Description Logics IJCAI 2019 Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games NeurIPS 2019