# Computer Science and Discrete Mathematics (CSDM)

## Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit of only n^O(k^3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME[n^(log n)^O(1)]. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS'02] which only held for larger nondeterministic classes such as NEXP.

## Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing (Continued)

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, “commutative” metric (for which the above problem is not convex).

## Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, “commutative” metric (for which the above problem is not convex).

## Abstract Convexity, Weak Epsilon-Nets, and Radon Number

Let F be a family of subsets over a domain X that is closed under taking intersections. Such structures are abundant in various fields of mathematics such as topology, algebra, analysis, and more. In this talk we will view these objects through the lens of *convexity*.

We will focus on an abstraction of the notion of *weak epsilon nets*:

given a distribution on the domain X and epsilon>0,

a weak epsilon net for F is a set of points that intersects any set in F with measure at least epsilon.

## Boolean function analysis: beyond the Boolean cube (continued).

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the focus is on results which are independent of the dimension.

## Boolean function analysis: beyond the Boolean cube.

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the focus is on results which are independent of the dimension.

## On the Communication Complexity of Classification Problems

We will discuss a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform a learning task. For example, consider the following problem of Convex Set Disjointness: In this instance Alice and Bob each receive a set of examples in Euclidean space and they need to decide if there exists a hyper-plane that separate the sets.

## A Tight Bound for Hypergraph Regularity

The hypergraph regularity lemma — the extension of Szemeredi's graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of this lemma, obtained by Gowers, Rodl et al. and Tao. Unfortunately, what all these proofs have in common is that they yield partitions whose order is given by the k-th Ackermann function.

## Some closure results for polynomial factorization

In a sequence of extremely fundamental results in the 80's, Kaltofen showed that any factor of n-variate polynomial with degree and arithmetic circuit size poly(n) has an arithmetic circuit of size poly(n). In other words, the complexity class VP is closed under taking factors.

A very basic question in this context is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, bounded depth arithmetic circuits or the class VNP, are closed under taking factors.