Journal of the American Mathematical Society

Công bố khoa học tiêu biểu

* Dữ liệu chỉ mang tính chất tham khảo

Sắp xếp:  
Non-commutative circuits and the sum-of-squares problem
Journal of the American Mathematical Society - Tập 24 Số 3 - Trang 871-898
Pavel Hrubeš, Avi Wigderson, Amir Yehudayoff

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree-four polynomials, the classical sum-of-squares problem: find the smallest n n such that there exists an identity ( 0.1 ) ( x 1 2 + x 2 2 + + x k 2 ) ( y 1 2 + y 2 2 + + y k 2 ) = f 1 2 + f 2 2 + + f n 2 , \begin{equation*} (0.1)\quad \quad (x_1^2+x_2^2+\cdots + x_k^2)\cdot (y_1^2+y_2^2+\cdots + y_k^2)= f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} , \quad \quad \end{equation*} where each f i = f i ( X , Y ) f_{i} = f_i(X,Y) is a bilinear form in X = { x 1 , , x k } X=\{x_{1},\dots ,x_{k}\} and Y = { y 1 , , y k } Y=\{y_{1},\dots , y_{k}\} . Over the complex numbers, we show that a sufficiently strong superlinear lower bound on n n in (0.1), namely, n k 1 + ϵ n\geq k^{1+\epsilon } with ϵ > 0 \epsilon >0 , implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

More generally, we consider such sum-of-squares identities for any biqua- dratic polynomial h ( X , Y ) h(X,Y) , namely ( 0.2 ) h ( X , Y ) = f 1 2 + f 2 2 + + f n 2 . \begin{equation*} (0.2) \quad \quad \qquad \quad \quad \quad \quad h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} . \quad \quad \qquad \quad \quad \quad \quad \end{equation*} Again, proving n k 1 + ϵ n\geq k^{1+\epsilon } in (0.2) for any explicit h h over the complex numbers gives an exponential lower bound for the non-commutative permanent. Our proofs rely on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of Valiant’s completeness of the permanent.

We prove such a superlinear bound in one special case. Over the real numbers, we construct an explicit biquadratic polynomial h h such that n n in (0.2) must be at least Ω ( k 2 ) \Omega (k^{2}) . Unfortunately, this result does not imply circuit lower bounds. We also present other structural results about non-commutative arithmetic circuits. We show that any non-commutative circuit computing an ordered non-commutative polynomial can be efficiently transformed to a syntactically multilinear circuit computing that polynomial. The permanent, for example, is ordered. Hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds. We also prove an exponential lower bound on the size of a non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.

Well-posedness in Sobolev spaces of the full water wave problem in 3-D
Journal of the American Mathematical Society - Tập 12 Số 2 - Trang 445-495
Sijue Wu

We consider the motion of the interface of a 3-D inviscid, incompressible, irrotational water wave, with air region above water region and surface tension zero. We prove that the motion of the interface of the water wave is not subject to Taylor instability, as long as the interface separates the whole 3-D space into two simply connected C 2 C^{2} regions. We prove further the existence and uniqueness of solutions of the full 3-D water wave problem, locally in time, for any initial interface that separates the whole 3-D space into two simply connected regions.

Supersimple theories
Journal of the American Mathematical Society - Tập 14 Số 1 - Trang 109-124
Steven Buechler, Anand Pillay, Frank Olaf Wagner

We prove elimination of hyperimaginaries in supersimple theories. This means that if an equivalence relation on the set of realisations of a complete type (in a supersimple theory) is defined by a possibly infinite conjunction of first order formulas, then it is the intersection of definable equivalence relations.

The Vlasov-Poisson-Landau system in a periodic box
Journal of the American Mathematical Society - Tập 25 Số 3 - Trang 759-812 - 2012
Yan Guo
Global classical solutions of the Boltzmann equation without angular cut-off
Journal of the American Mathematical Society - Tập 24 Số 3 - Trang 771-847
Philip T. Gressman, Robert M. Strain

This work proves the global stability of the Boltzmann equation (1872) with the physical collision kernels derived by Maxwell in 1866 for the full range of inverse-power intermolecular potentials,r(p1)r^{-(p-1)}withp>2p>2, for initial perturbations of the Maxwellian equilibrium states, as announced in an earlier paper by the authors. We more generally cover collision kernels with parameterss(0,1)s\in (0,1)andγ\gammasatisfyingγ>n\gamma > -nin arbitrary dimensionsTn×Rn\mathbb {T}^n \times \mathbb {R}^nwithn2n\ge 2. Moreover, we prove rapid convergence as predicted by the celebrated BoltzmannHH-theorem. Whenγ2s\gamma \ge -2s, we have exponential time decay to the Maxwellian equilibrium states. Whenγ>2s\gamma >-2s, our solutions decay polynomially fast in time with any rate. These results are completely constructive. Additionally, we prove sharp constructive upper and lower bounds for the linearized collision operator in terms of a geometric fractional Sobolev norm; we thus observe that a spectral gap exists only whenγ2s\gamma \ge -2s, as conjectured by Mouhot and Strain. It will be observed that this fundamental equation, derived by both Boltzmann and Maxwell, grants a basic example where a range of geometric fractional derivatives occur in a physical model of the natural world. Our methods provide a new understanding of the grazing collisions in the Boltzmann theory.

New extremal problems for the Riemannian recognition program via Alexandrov geometry
Journal of the American Mathematical Society - Tập 8 Số 1 - Trang 1-28
Karsten Grove, Steen Markvorsen
Kazhdan-Lusztig polynomials and character formulae for the Lie superalgebra 𝔤𝔩(𝔪|𝔫)
Journal of the American Mathematical Society - Tập 16 Số 1 - Trang 185-231
Jonathan Brundan

We compute the characters of the finite dimensional irreducible representations of the Lie superalgebragl(m|n)\mathfrak {gl}(m|n), and determineExt{\operatorname {Ext}}’s between simple modules in the category of finite dimensional representations. We formulate conjectures for the analogous results in categoryO\mathcal O. The combinatorics parallels the combinatorics of certain canonical bases over the Lie algebragl()\mathfrak {gl}(\infty ).

A bilinear estimate with applications to the KdV equation
Journal of the American Mathematical Society - Tập 9 Số 2 - Trang 573-603
Carlos E. Kenig, Gustavo Ponce, Luis Vega
On the size of Kakeya sets in finite fields
Journal of the American Mathematical Society - Tập 22 Số 4 - Trang 1093-1097
Zeev Dvir

A Kakeya set is a subset of F n \mathbb {F}^n , where F \mathbb {F} is a finite field of q q elements, that contains a line in every direction. In this paper we show that the size of every Kakeya set is at least C n q n C_{n} \cdot q^{n} , where C n C_{n} depends only on n n . This answers a question of Wolff.

A restriction estimate using polynomial partitioning
Journal of the American Mathematical Society - Tập 29 Số 2 - Trang 371-413
Larry Guth

If S S is a smooth compact surface in R 3 \mathbb {R}^3 with strictly positive second fundamental form, and E S E_S is the corresponding extension operator, then we prove that for all p > 3.25 p > 3.25 , E S f L p ( R 3 ) C ( p , S ) f L ( S ) \| E_S f\|_{L^p(\mathbb {R}^3)} \le C(p,S) \| f \|_{L^\infty (S)} . The proof uses polynomial partitioning arguments from incidence geometry.

Tổng số: 37   
  • 1
  • 2
  • 3
  • 4