NYCAC 2022 - Abstracts

Abstracts

To Monitorability and Beyond
Antonis Achilleos

I will give an overview of our work on the theoretical foundations of runtime verification over the past few years. Monitorability, i.e. the amenability of a specification to verification by monitors, has been a central theme in our work. I will demonstrate the insights that we have gained about its meaning and properties. Another theme that I will focus on is extending our monitoring framework to different settings. The goal is to verify more properties. We choose to use an operational approach and an expressive logic with a linear-time and a branching-time interpretation. I will explain how these decisions inform our work.

Kolmogorov Complexity Characterizes Statistical Zero Knowledge
Eric Allender

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge (SZK), as well as the related classes NISZK_L and SZK_L. As a by-product, this yields a new approach to the NP vs NL question.
This is joint work with Shuichi Hirahara and Harsha Tirumala. A paper is available as ECCC TR22-127, and it will be presented at ITCS 2023.

A logical characterization of self-reducible counting problems the decision version of which is easy
Aggela Chalki

In the area of descriptive complexity, complexity classes are characterized by the type of logic that is needed to express the problems in them. Fagin's fundamental theorem states that the set of all languages expressible in existential second-order logic is the class NP. In this talk we are going to discuss descriptive complexity for counting classes. #P, which was introduced by Valiant, is the class of functions that count the number of solutions to problems in NP, and it has been characterized in two different ways. We focus on the class TotP, which contains all self-reducible #P functions the decision version of which is easy. Problems in TotP are of great interest, since they are counting problems that are eligible to be approximable. It is also a class that has a simple structural characterization, natural complete problems and nice closure properties. Although several subclasses of TotP have been characterized in the context of descriptive complexity, a logical characterization of TotP is missing. We are going to define a logic equipped with recursion and prove that captures TotP. Moreover, based on the syntax of this logic, and by extending it, we are going to provide a logical characterization of the class of functions that are computable in polynomial space, namely FPSPACE.

Approximate Representation Learning from Non-Metric Constraints
Vaggos Chatziafratis

Metric embeddings study how to map n items of interest to a target metric space such that distance lengths are not heavily distorted. But what if we only care to preserve the relative ordering of the distances? Such order-preserving embeddings naturally arise in important applications ---recommendations, crowdsourcing, psychometrics, ranking, nearest-neighbor search--- and have been studied since the 1950s under the name of Non-Metric Embeddings. In this talk, we investigate a basic question in machine learning based on qualitative information. An important example of such questions is the following: given triplet constraints of the form ``item i is closer to item j than to item k,'' can we find low-dimensional Euclidean representations, or even non-Euclidean representations (like a hierarchy) for the n items that respect those triplet constraints? We will see two cases where we can obtain nearly-tight upper and lower bounds.

The talk will be based on recent joint works with Piotr Indyk (MIT) and with Kostya Makarychev (Northwestern).

The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ

Markov Decision Processes (MDP) are a fundamental model for dynamic optimization in a stochastic environment with applications in many areas, including operations research, artificial intelligence, game theory, robotics, control theory, and verification. Policy iteration is a family of greedy algorithms used to find an optimal policy (choice of action for each node) of an MDP. While policy iteration converges quickly in practice, many of its variants have exponential runtime in the worst case. To reconcile a similar gap between slow worst-case and quick practical runtime for the Simplex algorithm, Spielman and Teng introduced smoothed analysis and showed that the smoothed complexity of Simplex under a certain pivoting rule is polynomial. Given the similarity of Simplex and policy iteration, some variants of which are in fact equivalent, one might hope to show that the smoothed complexity of policy iteration is also polynomial. However, we show the contrary: that for several of the most common policy iteration variants, the smoothed complexity is subexponential or exponential. This is joint work with Mihalis Yannakakis.

Learning-Augmented Mechanism Design
Vasilis Gkatzelis

This talk will introduce the model of “learning-augmented mechanism design” (or “mechanism design with predictions”), which is an alternative model for the design and analysis of mechanisms in strategic settings. Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, recent work on “algorithms with predictions” has developed algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use this information to guide their decisions and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining good worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, most of these results have been limited to online algorithms but some very recent work has shown that a possibly even more fertile ground for this model is in mechanism design. This talk will cover the foundations of learning-augmented mechanism design and some recent results in this model.

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Lane A. Hemaspaandra

Cai and Hemachandra used iterative constant-setting to prove that Few \subseteq ParityP (and thus that FewP \subseteq ParityP). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant's unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_{PRIMES}.
This is joint work with Mandar Juvekar (Boston U.), Arian Nadjimzadah (UCLA), and Patrick A. Phillips (Riverside Research).

Structure and Complexity of Bag Consistency
Phokion G. Kolaitis

Acyclic hypergraphs are well known to give rise to database schemas with desirable structural and algorithmic properties. In particular, the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for relations over that schema holds, which means that every collection of pairwise consistent relations over the schema is globally consistent. In this talk, we present results about the interplay between local and global consistency for bags (multisets). The first main result asserts that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for bags over that schema holds. The second main result is a dichotomy theorem for the computational complexity of the global consistency problem for bags: if the schema is acyclic, then the global consistency problem for bags is solvable in polynomial time, while if the schema is cyclic, then the global consistency problem for bags is NP-complete. The latter result contrasts sharply with the state of affairs for relations, where, for each fixed schema, the global consistency problem for relations is solvable in polynomial time.
This is joint work with Albert Atserias at UPC, Barcelona.

Convex Influences
Shivam Nadimpalli

We introduce a new notion of influence—called "convex influence"—for symmetric convex symmetric sets over Gaussian space which has many of the properties of influences of Boolean functions over the discrete cube. Our main results for convex influences give Gaussian space analogues of many important results on influences for monotone Boolean functions including the Kahn-Kalai-Linial theorem, a sharp threshold theorem of Kalai, and a quantitative correlation inequality due to Talagrand. We will also discuss a recent application of convex influences to the problem of distinguishing Gaussians truncated by a convex set.
Based on joint works with Anindya De and Rocco A. Servedio.

The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
Manolis Vlatakis

Introduced by the celebrated works of Debreu and Rosen in the 1950s and 60s, concave n-person games have found many important applications in Economics and Game Theory. We characterize the computational complexity of finding an equilibrium in such games. We show that a general formulation of this problem belongs to PPAD, and that finding an equilibrium is PPAD-hard even for a rather restricted games of this kind: strongly-convex utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. Along the way we provide a general computational formulation of Kakutani's Fixed Point Theorem, previously formulated in a special case that is too restrictive to be useful in reductions, and prove it PPAD-complete.
This is joint work with Christos H. Papadimitriou and Manolis Zampetakis.