More Like this

1. Dimension of the Exceptional Set in the Aronszajn–Donoghue Theorem for Finite Rank Perturbations

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

   Liaw, Constanze; Treil, Sergei; Volberg, Alexander (November 2020, International Mathematics Research Notices)

   null (Ed.)

   Abstract The classical Aronszajn–Donoghue theorem states that for a rank-one perturbation of a self-adjoint operator (by a cyclic vector) the singular parts of the spectral measures of the original and perturbed operators are mutually singular. As simple direct sum type examples show, this result does not hold for finite rank perturbations. However, the set of exceptional perturbations is pretty small. Namely, for a family of rank $$d$$ perturbations $$A_{\boldsymbol{\alpha }}:= A + {\textbf{B}} {\boldsymbol{\alpha }} {\textbf{B}}^*$$, $${\textbf{B}}:{\mathbb C}^d\to{{\mathcal{H}}}$$, with $${\operatorname{Ran}}{\textbf{B}}$$ being cyclic for $$A$$, parametrized by $$d\times d$$ Hermitian matrices $${\boldsymbol{\alpha }}$$, the singular parts of the spectral measures of $$A$$ and $$A_{\boldsymbol{\alpha }}$$ are mutually singular for all $${\boldsymbol{\alpha }}$$ except for a small exceptional set $$E$$. It was shown earlier by the 1st two authors, see [4], that $$E$$ is a subset of measure zero of the space $$\textbf{H}(d)$$ of $$d\times d$$ Hermitian matrices. In this paper, we show that the set $$E$$ has small Hausdorff dimension, $$\dim E \le \dim \textbf{H}(d)-1 = d^2-1$$. 

   more » « less
2. Some complexity results in the theory of normal numbers

   https://doi.org/10.4153/S0008414X20000723  

   Airey, Dylan; Jackson, Steve; Mance, Bill (February 2022, Canadian Journal of Mathematics)

   Abstract Let $$\mathcal {N}(b)$$ be the set of real numbers that are normal to base b . A well-known result of Ki and Linton [19] is that $$\mathcal {N}(b)$$ is $$\boldsymbol {\Pi }^0_3$$ -complete. We show that the set $${\mathcal {N}}^\perp (b)$$ of reals, which preserve $$\mathcal {N}(b)$$ under addition, is also $$\boldsymbol {\Pi }^0_3$$ -complete. We use the characterization of $${\mathcal {N}}^\perp (b),$$ given by Rauzy, in terms of an entropy-like quantity called the noise . It follows from our results that no further characterization theorems could result in a still better bound on the complexity of $${\mathcal {N}}^\perp (b)$$ . We compute the exact descriptive complexity of other naturally occurring sets associated with noise. One of these is complete at the $$\boldsymbol {\Pi }^0_4$$ level. Finally, we get upper and lower bounds on the Hausdorff dimension of the level sets associated with the noise. 

   more » « less
3. A Spanner for the Day After

   https://doi.org/10.1007/s00454-020-00228-6  

   Buchin, Kevin; Har-Peled, Sariel; Oláh, Dániel (December 2020, Discrete & Computational Geometry)

   null (Ed.)

   Abstract We show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for any k , and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion. 

   more » « less
4. Certified Hardness vs. Randomness for Log-Space

   https://doi.org/10.1109/FOCS57990.2023.00061  

   Pyne, Edward; Raz, Ran; Zhan, Wei: (November 2023, 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023)

   Let L be a language that can be decided in linear space and let ϵ>0 be any constant. Let A be the exponential hardness assumption that for every n, membership in L for inputs of length n cannot be decided by circuits of size smaller than 2ϵn. We prove that for every function f:{0,1}∗→{0,1}, computable by a randomized logspace algorithm R, there exists a deterministic logspace algorithm D (attempting to compute f), such that on every input x of length n, the algorithm D outputs one of the following:1)The correct value f(x).2)The string: “I am unable to compute f(x) because the hardness assumption A is false”, followed by a (provenly correct) circuit of size smaller than 2ϵn′ for membership in L for inputs of length n′, for some n′=Θ(logn); that is, a circuit that refutes A. Moreover, D is explicitly constructed, given R.We note that previous works on the hardness-versus-randomness paradigm give derandomized algorithms that rely blindly on the hardness assumption. If the hardness assumption is false, the algorithms may output incorrect values, and thus a user cannot trust that an output given by the algorithm is correct. Instead, our algorithm D verifies the computation so that it never outputs an incorrect value. Thus, if D outputs a value for f(x), that value is certified to be correct. Moreover, if D does not output a value for f(x), it alerts that the hardness assumption was found to be false, and refutes the assumption.Our next result is a universal derandomizer for BPL (the class of problems solvable by bounded-error randomized logspace algorithms) 1 : We give a deterministic algorithm U that takes as an input a randomized logspace algorithm R and an input x and simulates the computation of R on x, deteriministically. Under the widely believed assumption BPL=L, the space ... 

   more » « less
5. Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $$~O(n\sqrt{d})$$ Monotonicity Tester

   Hadley Black, Deeparnab Chakrabarty (June 2023, Proceedings of the annual ACM Symposium on Theory of Computing)

   The problem of testing monotonicity for Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $$\otilde(\eps^{-2}\sqrt{d})$$ queries. Up to polylog $$d$$ and $$\eps$$ factors, this bound matches the $$\widetilde{\Omega}(\sqrt{d})$$-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any $n > 2$, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a $$\otilde(d^{5/6})$$-query upper bound (SODA 2020), quite far from the $$\sqrt{d}$$ bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant $$n$$, up to $$\poly(\eps^{-1}\log d)$$ factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making $$\otilde(\eps^{-2}n\sqrt{d})$$ queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid $[n]^d$. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube. 

   more » « less