Abstracts
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity
Eric Allender
A version of time-bounded Kolmogorov complexity, denoted KT, has
received attention in the past several years, due to its close
connection to circuit complexity and to the Minimum Circuit Size Problem
MCSP. Essentially all results about the complexity of MCSP hold also for
MKTP (the problem of computing the KT complexity of a string). Both MKTP
and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing
reductions; neither is known to be NP-complete. Recently, some hardness
results for MKTP were proved that are not (yet) known to hold for MCSP.
In particular, MKTP is hard for DET (a subclass of P) under nonuniform
NC^0 m-reductions.
We improve this, to show that MKTP is hard for the (apparently larger)
class NISZK_L under not only NC^0 m-reductions but even under
projections. Also MKTP is hard for NISZK under P/poly m-reductions.
Here, NISZK is the class of problems with non-interactive zero-knowledge
proofs, and NISZK_L is the non-interactive version of the class SZK_L
that was studied by Dvir et al.
As an application, we provide several improved worst-case to
average-case reductions to problems in NP.
This is joint work with John Gouwar, Shuichi Hirahara, and Caleb Robelle.
slides
Webex meeting recording: NYCAC 20-21-20210319 1404-3
Recording link:
here
Crowd Verifiable Zero-Knowledge and End-to-end Verifiable Multiparty Computation
Foteini Baldimtsi
Auditing a secure multiparty computation (MPC) protocol entails the validation of the protocol transcript by a third party that is otherwise untrusted. In this work we introduce the concept of end-to-end verifiable MPC (VMPC), that requires the validation to provide a correctness guarantee even in the setting that all servers, trusted setup primitives and all the client systems utilized by the input-providing users of the MPC protocol are subverted by an adversary. To instantiate VMPC, we introduce a new concept in the setting of zero-knowlegde protocols that we term crowd verifiable zero-knowledge (CVZK). A CVZK protocol enables a prover to convince a set of verifiers about a certain statement, even though each one individually contributes a small amount of entropy for verification and some of them are adversarially controlled. Given CVZK, we present a VMPC protocol that is based on discrete-logarithm related assumptions. At the high level of adversity that VMPC is meant to withstand, it is infeasible to ensure perfect correctness, thus we investigate the classes of functions and verifiability relations that are feasible in our framework, and present a number of possible applications the underlying functions of which can be implemented via VMPC.
Joint work with Aggelos Kiayias and Thomas Zacharias and Bingsheng Zhang
Webex meeting recording: NYCAC 20-21-20210319 1804-7
Recording link:
here
The Complexity of Online Bribery in Sequential Elections
Lane A. Hemaspaandra
Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all votes. However, in many real-world settings votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to alter a given vote, and when making that decision the briber may not know what votes remaining voters will cast.
We introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is polynomial-time computable, an online, sequential setting may vastly increase the complexity of bribery, jumping the problem up to completeness for high levels of the polynomial hierarchy or even PSPACE. But we also show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems.
This is joint work with Edith Hemaspaandra and Joerg Rothe.
slides
Webex meeting recording: NYCAC 20-21-20210319 1555-5
Recording link:
here
Computational Social Choice and Incomplete Information
Phokion G. Kolaitis
Computational social choice is an interdisciplinary field that studies collective decision making from an algorithmic perspective. Determining the winners under various voting rules is a mainstream area of research in computational social choice. Many such rules assume that the voters provide complete information about their preferences, an assumption that is often unrealistic because typically only partial preference information is available. This state of affairs has motivated the study of the notions of the necessary winners and the possible winners with respect to a variety of voting rules.
The main aim of this talk is to present an overview of winner determination under incomplete information and to highlight some recent advances in this area, including the development of a framework that aims to create bridges between computational social choice and data management. This framework infuses relational database context into social choice and gives rise to
to the notions of the necessary answers and the possible answers to queries involving voting rules, candidates, voters, issues, and positions on issues.
slides
Webex meeting recording: NYCAC 20-21-20210319 1847-8
Recording link:
here
Learning in Zero-Sum Games Revisited:
Equilibration, Optimization, Recurrence & Chaos
Georgios Piliouras
We examine some classic questions in game theory and online learning. How do standard regret-minimizing dynamics such as multiplicative weights update, online gradient descent, and follow-the-regularized-leader behave when applied in zero-sum games? The standard textbook answer to this question is that these dynamics "converge" in a time-average sense to equilibria. We instead focus on understanding the day-to-day behavior. Continuous-time dynamics "cycle" around the equilibrium, whereas naive discretizations (e.g. simultaneous gradient descent ascent) result in unstable and chaotic behavior. On the other hand, alternating gradient descent ascent leads again to cyclic/recurrent behavior. We offer a unified perspective to understand these results combining tools from optimization theory (regret analysis), dynamical systems (chaos theory) and physics (Hamiltonians).
Bio: Dr. Piliouras is an assistant professor at the Singapore University of Technology and Design (SUTD). He received his PhD in Computer Science from Cornell University in 2010. He has held postdoc positions at the Georgia Institute of Technology (GaTech, ECE Dept.) and California Institute of Technology (Caltech, Dept. of Computing and Mathematical Sciences). He has held visiting positions at UC Berkeley and DeepMind. He is the recipient of a Singapore NRF Fellowship (2018), a Simons/UC Berkeley Fellowship (2015), a best paper nomination at AAMAS (2019) and a best paper award at AAAI (2021).
Webex meeting recording: NYCAC 20-21-20210319 1212-1
Recording link:
here
The Complexity of Constrained Min-Max Optimization
Stratis Skoulakis
Despite its important applications in Machine Learning, min-max optimization
of objective functions that are
nonconvex-nonconcave remains elusive.
Not only are there no known first-order methods converging even to approximate
local min-max points, but the computational complexity of identifying them is
also poorly understood. In this paper, we provide a characterization of the
computational complexity of the problem, as well as of the limitations of
first-order methods in constrained min-max optimization problems with
nonconvex-nonconcave objectives and linear constraints.
As a warm-up, we show that, even when the objective is a Lipschitz and
smooth differentiable function, deciding whether a min-max point exists, in
fact even deciding whether an approximate min-max point exists, is NP-hard.
More importantly, we show that an approximate local min-max point of large
enough approximation is guaranteed to exist, but finding one such point is
PPAD-complete. The same is true of computing an approximate fixed point of
the (Projected) Gradient Descent/Ascent update dynamics.
An important byproduct of our proof is to establish an unconditional
hardness result in the Nemirovsky Yudin oracle
optimization model. We show that, given oracle access to some function
$f : \calP \to [-1, 1]$ and its gradient
$\nabla f$, where
$\calP \subseteq [0, 1]^d$ is a known convex polytope, every algorithm that
finds a
$\eps$-approximate local min-max point needs to make a number of
queries that is exponential in at least one of
$1/\eps$, L, G, or d,
where L and G are respectively the smoothness and Lipschitzness of f and
d is the dimension. This comes in sharp contrast to minimization problems,
where finding approximate local minima in the same setting can be done
with Projected Gradient Descent using
$O(L/\eps)$ many queries. Our result is
the first to show an exponential separation between these two fundamental
optimization problems in the oracle model.
Webex meeting recording: NYCAC 20-21-20210319 1303-2
Recording link:
here
Free Energy Wells and Overlap Gap Property in Sparse PCA
Ilias Zadik
In this talk we will present new results on the variant of the sparse PCA model where one seeks to recover a binary k-sparse binary-valued spike x from observations of the form $Y=\lambda xx^t+W$ where $W$ is a GOE matrix and $\lambda>0$. A large line of research suggests the rise of a ``hard" regime, that is the existence of some values of $\lambda$ for which recovery is possible in exponential time but not in polynomial time. Furthermore, some recent work by [Ding et al'2019] analyzed the performance of low-degree polynomial estimators for this recovery task and conjectured the exact subexponential time needed to recover, for all the values of $\lambda$ in the hard regime.
We will discuss some new results on the local dynamics of the recovery problem of interest, which establish that a large family of MCMC methods also requires the same subexponential time conjectured in [Ding et al '2019] to succeed in the hard regime. The results are obtained by establishing the presence of the Overlap Gap Property and Free Energy Wells in the landscape of the problem, which are geometric properties introduced in the theory of spin glasses.
This is joint work with Gérard Ben Arous and Alexander Wein.
Webex meeting recording: NYCAC 20-21-20210319 1715-6
Recording link:
here
Conditional PAC-Bayes and Mutual Information Generalization Bounds: Fast rates that handle general VC classes
Lydia Zakynthinou
PAC-Bayesian as well as mutual information (MI) generalization error bounds are standard approaches that have proven very useful in the study of the generalization properties of machine learning algorithms. However, recent work has shown a deficiency of such bounds: there exist VC classes for which MI and PAC-Bayes generalization error bounds must remain trivial (Bassily et al. 2018, Livni and Moran 2020), even though the theory of uniform convergence guarantees generalization in this case. To avoid the impossibility result for MI, we have introduced a new framework, that of conditional MI (Steinke and Zakynthinou 2020), which unifies MI, uniform convergence (VC), differential privacy and other approaches.
We now give a novel, unified derivation of conditional PAC-Bayesian and MI generalization bounds, which allows us to get nontrivial bounds for general VC classes. Moreover, it allows us to get fast rates of order O((COMPLEXITY/n)^γ) for γ>1/2 if a Bernstein condition holds and for exp-concave losses (with γ=1), which is impossible with both standard PAC-Bayes and MI generalization bounds.
Joint work with Peter Grünwald (CWI) and Thomas Steinke (Google Brain).
Webex meeting recording: NYCAC 20-21-20210319 1504-4
Recording link:
here