I will continue to describe deterministic algorithms for approximately counting common bases of matroids within an exponential factor. This is based on AOVI and previous works of AO.
A multivariate complex polynomial is called stable if any line in any positive direction meets its hypersurface only at real points. Stable polynomials have close relations to matroids and hyperbolic programming. We will discuss a generalization of stability to algebraic varieties of codimension larger than one. They are varieties which are hyperbolic with respect to the nonnegative Grassmannian, following the notion of hyperbolicity studied by Shamovich, Vinnikov, Kummer, and Vinzant. We show that their tropicalization and Chow polytopes have nice combinatorial structures related to braid arrangements and positroids, generalizing some results of Choe, Oxley, Sokal, Wagner, and Brändén on Newton polytopes and tropicalizations of stable polynomials. This is based on joint work with Felipe Rincón and Cynthia Vinzant.
One strategy for developing a proof of a claimed theorem is to start by understanding what a counter-example should look like. In this talk, we will discuss a few recent results in harmonic analysis that utilize a quantitative version of this approach. A key step is the solution of an inverse problem with the following flavor. Let $T:X \to Y$ be a bounded linear operator and let $0 < a \leq \|T\|$. What can we say about those functions $f \in X$ obeying the reverse inequality $\|Tf\|_Y \geq a\|f\|_X$?
We discuss the problem of optimal mixing of an inhomogeneous distribution of a scalar field via an active control of the flow velocity, governed by the Stokes or the Navier-Stokes equations, in a two dimensional open bounded and connected domain. We consider the velocity field steered by a control input that acts tangentially on the boundary of the domain through the Navier slip boundary conditions. This is motivated by mixing within a cavity or vessel by moving the walls or stirring at the boundaries. Our main objective is to design an optimal Navier slip boundary control that optimizes mixing at a given final time. Non-dissipative scalars, both passive and active, governed by the transport equation will be discussed. In the absence of diffusion, transport and mixing occur due to pure advection. This essentially leads to a nonlinear control problem of a semi-dissipative system. We shall provide a rigorous proof of the existence of an optimal controller, derive the first-order necessary conditions for optimality, and present some preliminary results on the numerical implementation.
This talk is based on a paper by Grigoriy Blekherman. In most cases, nonnegative polynomials differ from positive polynomials. We will discuss precisely what equations cause these differences, and relate them to the well known Cayley-Bacharach theorem for low degree polynomials.
I will talk about algorithms (with unlimited computational power) which adaptively probe pairs of vertices of a graph to learn the presence or absence of edges and whose goal is to output a large clique. I will focus on the case of the random graph G(n,1/2), in which case the size of the largest clique is roughly 2\log(n). Our main result shows that if the number of pairs queried is linear in n and adaptivity is restricted to finitely many rounds, then the largest clique cannot be found; more precisely, no algorithm can find a clique larger than c\log(n) where c < 2 is an explicit constant. I will also discuss this question in the planted clique model. This is based on joint works with Uriel Feige, David Gamarnik, Joe Neeman, Benjamin Schiffer, and Prasad Tetali.
When Alice wants to send a k-bits message v to Bob over a noisy channel, she encodes it as a longer n-bits message Mv, where M is a n times k matrix over F_2. The minimal distance d_M of the linear code M is defined as the minimum Hamming distance between Mw and Mu over all distinct points w,u in F_2^k. In this way, if there are less than d_M/2 corrupted bits in the message, Bob can recover the original message via a nearest neighbor search algorithm.
The classical Gilbert-Varshamov Bound provides a lower bound for d_M if the columns of M are independent copies of X, where X is the random vector uniformly distributed on F_2^n. Under the same assumption on M, we show that the distribution of d_M is essentially the same as the minimum of Hamming weight (Hamming distance to origin) of 2^k-1 i.i.d copies of X.
The result is surprising since M is only generated by k independent copies of X. Furthermore, our results also work for arbitrary finite fields.
This is joint work with Jing Hao, Galyna Livshyts, Konstantin Tikhomirov.
We will discuss a novel approach to obtaining non-asymptotic estimates on the lower tail of the least singular value of an $n \times n$ random matrix $M_{n} := M + N_{n}$, where $M$ is a fixed matrix with operator norm at most $O(\exp(n^{c}))$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a random variable with mean 0 and variance 1. This has been previously considered in a series of works by Tao and Vu, and our results improve upon theirs in two ways:
(i) We are able to deal with $\|M\| = O(\exp(n^{c}))$ whereas previous work was applicable for $\|M\| = O(\poly(n))$.
(ii) Even for $\|M\| = O(poly(n))$, we are able to extract more refined information – for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(exp(-n^{c}))$, whereas even in the case when $N_n$ is an i.i.d. Bernoulli matrix, the results of Tao and Vu only give inverse polynomial singularity probability.
The emergent shape of a knitted fabric is highly sensitive to the underlying stitch pattern. Here, by a stitch pattern we mean a periodic array of symbols encoding a set of rules or instructions performed to produce a swatch or a piece of fabric. So, it is crucial to understand what exactly these instructions mean in terms of mechanical moves performed using a yarn (a smooth piece of string) and a set of knitting needles (oriented sticks). Motivated by the fact that locally every knitting move results in a slip knot, we use tools from topology to model the set of all doubly periodic stitch patterns, knittable & non-knittable, as knots & links in a three manifold. Specifically, we define a map from the set of doubly-periodic stitch patterns to the set of links in S^3 and use link invariants such as the linking number, multivariable Alexander polynomial etc. to characterize them. We focus on such links derived from knitted stitch patterns in an attempt to tackle the question: whether or not a given stitch pattern can be realized through knitting.
Brascamp-Lieb inequalities are estimates for certain multilinear forms on functions on Euclidean spaces. They generalize several classical inequalities, such as Hoelder's inequality or Young's convolution inequality. In this talk we consider singular Brascamp-Lieb inequalities, which arise when one of the functions in the Brascamp-Lieb inequality is replaced by a singular integral kernel. Examples include multilinear singular integral forms such as paraproducts or the multilinear Hilbert transform. We survey some results in the area.
