Summation formulae and speculations on period integrals attached to triples of automorphic representations

Jayce Getz
Duke University; Member, School of Mathematics
March 27, 2018

Braverman and Kazhdan have conjectured the existence of summation formulae that are essentially equivalent to the analytic continuation and functional equation of Langlands L-functions in great generality. Motivated by their conjectures and related conjectures of L. Lafforgue, Ngo, and Sakellaridis, Baiying Liu and I have proven a summation formula analogous to the Poisson summation formula for the subscheme cut out of three quadratic spaces $(V_i,Q_i)$ of even dimension by the equation
 
$Q_1(v_1)=Q_2(v_2)=Q_3(v_3)$.
 

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

Cody Murray
Massachusetts Institute of Technology
March 26, 2018

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)

Yuanzhi Li
Princeton University
March 20, 2018

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

Yuanzhi Li
Princeton University
March 19, 2018

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).