Theory

Tight Inapproximability for Graphical Games AAAI 2023 Voting with Preference Intensities AAAI 2023 A framework for bilevel optimization that enables stochastic and global variance reduction algorithms NeurIPS 2022 All Politics is Local: Redistricting via Local Fairness NeurIPS 2022 Dimensionality and Coordination in Voting: The Distortion of STV AAAI 2022 Efficient Convex Optimization Requires Superlinear Memory COLT 2022 Estimation of Entropy in Constant Space with Improved Sample Complexity NeurIPS 2022 Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods NeurIPS 2022 Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization NeurIPS 2022 Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity NeurIPS 2022 Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation AAAI 2022 On Learning and Refutation in Noninteractive Local Differential Privacy NeurIPS 2022 On the Effectiveness of Iterative Learning Control L4DC 2022 Pizza Sharing Is PPA-Hard AAAI 2022 Reconstruction on Trees and Low-Degree Polynomials NeurIPS 2022 Revision by Comparison for Ranking Functions IJCAI 2022 Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis NeurIPS 2022 The Complexity of Subelection Isomorphism Problems AAAI 2022 Tractable Abstract Argumentation via Backdoor-Treewidth AAAI 2022 Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula AAAI 2022 An analysis of Ermakov-Zolotukhin quadrature using kernels NeurIPS 2021 Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD NeurIPS 2021 Outside Computation with Superior Functions NAACL 2021 Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework AAAI 2021 Parametric Complexity Bounds for Approximating PDEs with Neural Networks NeurIPS 2021