More Like this

1. Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

   https://doi.org/10.1093/qmath/haz022  

   Basu, Saugata ; Lerario, Antonio ; Natarajan, Abhiram ( October 2019 , The Quarterly Journal of Mathematics)

   Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n-1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n-1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n-2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalyticmore »hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$, a subsequence $\{a_{d_m}\}_{m\in \mathbb{N}}$ and homogeneous polynomials $\{p_{m}\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $b_k$ denotes the $k$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $\Gamma$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $d$, of the set $\Sigma _{d_m,a, \Gamma }$ of polynomials verifying (0.1) is positive, but there exists a constant $c_\Gamma$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $a$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $\Gamma$, for most polynomials a Bézout-type bound holds for the intersection $\Gamma \cap Z(p)$: for every $0\leq k\leq n-2$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$

   « less
2. Edge Expansion and Spectral Gap of Nonnegative Matrices

   https://doi.org/10.1137/1.9781611975994.73  

   Mehta, Jenish C. ; Schulman, Leonard J. ( January 2020 , Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms)

   The classic graphical Cheeger inequalities state that if $M$ is an $n\times n$ \emph{symmetric} doubly stochastic matrix, then \[ \frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))} \] where $\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in S,j\not\in S}M_{i,j}\right)$ is the edge expansion of $M$, and $\lambda_{2}(M)$ is the second largest eigenvalue of $M$. We study the relationship between $\phi(A)$ and the spectral gap $1-\re\lambda_{2}(A)$ for \emph{any} doubly stochastic matrix $A$ (not necessarily symmetric), where $\lambda_{2}(A)$ is a nontrivial eigenvalue of $A$ with maximum real part. Fiedler showed that the upper bound on $\phi(A)$ is unaffected, i.e., $\phi(A)\leq\sqrt{2\cdot(1-\re\lambda_{2}(A))}$. With regards to the lower bound on $\phi(A)$, there are known constructions with \[ \phi(A)\in\Theta\left(\frac{1-\re\lambda_{2}(A)}{\log n}\right), \] indicating that at least a mild dependence on $n$ is necessary to lower bound $\phi(A)$. In our first result, we provide an \emph{exponentially} better construction of $n\times n$ doubly stochastic matrices $A_{n}$, for which \[ \phi(A_{n})\leq\frac{1-\re\lambda_{2}(A_{n})}{\sqrt{n}}. \] In fact, \emph{all} nontrivial eigenvalues of our matrices are $0$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $n$), by showing that for any doubly stochastic matrix $A$, \[ \phi(A)\geq\frac{1-\re\lambda_{2}(A)}{35\cdot n}. \] As a consequence, unlike the symmetric case, there is a (necessary) loss of amore »factor of $n^{\alpha}$ for $\frac{1}{2}\leq\alpha\leq1$ in lower bounding $\phi$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $R$ with nonnegative entries, to obtain a two-sided \emph{gapped} refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such $R$, there is a nonnegative eigenvalue $r$ such that all eigenvalues of $R$ lie within the closed disk of radius $r$ about $0$. Further, if $R$ is irreducible, which means $\phi(R)>0$ (for suitably defined $\phi$), then $r$ is positive and all other eigenvalues lie within the \textit{open} disk, so (with eigenvalues sorted by real part), $\re\lambda_{2}(R)« less
3. Energy Harvesting Performance of a Flapping Foil with Leading Edge Motion

   Prier, M. ( April 2019 , Dissertation)

   F or c e d at a f or a fl a p pi n g f oil e n er g y h ar v e st er wit h a cti v e l e a di n g e d g e m oti o n o p er ati n g i n t h e l o w r e d u c e d fr e q u e n c y r a n g e i s c oll e ct e d t o d et er mi n e h o w l e a di n g e d g e m oti o n aff e ct s e n er g y h ar v e sti n g p erf or m a n c e. T h e f oil pi v ot s a b o ut t h e mi dc h or d a n d o p er at e s i n t h e l o w r e d u c e d fr e q u e n c y r a n g e of 𝑓𝑓more »𝑓𝑓 / 𝑈𝑈 ∞ = 0. 0 6 , 0. 0 8, a n d 0. 1 0 wit h 𝑅𝑅 𝑅𝑅 = 2 0 ,0 0 0 − 3 0 ,0 0 0 , wit h a pit c hi n g a m plit u d e of 𝜃𝜃 0 = 7 0 ∘ , a n d a h e a vi n g a m plit u d e of ℎ 0 = 0. 5 𝑓𝑓 . It i s f o u n d t h at l e a di n g e d g e m oti o n s t h at r e d u c e t h e eff e cti v e a n gl e of att a c k e arl y t h e str o k e w or k t o b ot h i n cr e a s e t h e lift f or c e s a s w ell a s s hift t h e p e a k lift f or c e l at er i n t h e fl a p pi n g str o k e. L e a di n g e d g e m oti o n s i n w hi c h t h e eff e cti v e a n gl e of att a c k i s i n cr e a s e d e arl y i n t h e str o k e s h o w d e cr e a s e d p erf or m a n c e. I n a d diti o n a di s cr et e v ort e x m o d el wit h v ort e x s h e d di n g at t h e l e a di n g e d g e i s i m pl e m e nt f or t h e m oti o n s st u di e d; it i s f o u n d t h at t h e m e c h a ni s m f or s h e d di n g at t h e l e a di n g e d g e i s n ot a d e q u at e f or t hi s p ar a m et er r a n g e a n d t h e m o d el c o n si st e ntl y o v er pr e di ct s t h e a er o d y n a mi c f or c e s.« less
4. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil ; Williams, R. Ryan ( November 2022 , Theory of Computing Systems)

   We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

   #SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   #SAT algorithms for$2^{n^{{\varepsilon }}}$$2^{n^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$$2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomialmore »size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

   « less
5. Cycle-Complete Ramsey Numbers

   https://doi.org/10.1093/imrn/rnz119  

   Keevash, Peter ; Long, Eoin ; Skokan, Jozef ( July 2019 , International Mathematics Research Notices)

   The Ramsey number $r(C_{\ell },K_n)$ is the smallest natural number $N$ such that every red/blue edge colouring of a clique of order $N$ contains a red cycle of length $\ell $ or a blue clique of order $n$. In 1978, Erd̋s, Faudree, Rousseau, and Schelp conjectured that $r(C_{\ell },K_n) = (\ell -1)(n-1)+1$ for $\ell \geq n\geq 3$ provided $(\ell ,n) \neq (3,3)$. We prove that, for some absolute constant $C\ge 1$, we have $r(C_{\ell },K_n) = (\ell -1)(n-1)+1$ provided $\ell \geq C\frac{\log n}{\log \log n}$. Up to the value of $C$ this is tight since we also show that, for any $\varepsilon>0$ and $n> n_0(\varepsilon )$, we have $r(C_{\ell }, K_n) \gg (\ell -1)(n-1)+1$ for all $3 \leq \ell \leq (1-\varepsilon )\frac{\log n}{\log \log n}$. This proves the conjecture of Erd̋s, Faudree, Rousseau, and Schelp for large $\ell $, a stronger form of the conjecture due to Nikiforov, and answers (up to multiplicative constants) two further questions of Erd̋s, Faudree, Rousseau, and Schelp.