More Like this

1. Near-optimal fitting of ellipsoids to random points

   Potechin, Aaron; Turner, Paxton M.; Venkat, Prayaag; Wein, Alexander S. (July 2023, Proceedings of Machine Learning Research)

   Given independent standard Gaussian points v1, . . . , vn in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, Saunderson, Parrilo, and Willsky (Saunderson, 2011; Saunderson et al., 2013) conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ∼ d^2/4. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some n = d^2/polylog(d). Our proof demonstrates feasibility of the least squares construction of (Saunderson, 2011; Saunderson et al., 2013) using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices. 

   more » « less
2. SDR Proof-of-Concept of Full-Duplex Jamming for Enhanced Physical Layer Security

   https://doi.org/10.3390/s21030856  

   Silva, André; Gomes, Marco; Vilela, João P.; Harrison, Willie K. (February 2021, Sensors)

   In order to secure wireless communications, we consider the usage of physical-layer security (PLS) mechanisms (i.e., coding for secrecy mechanisms) combined with self-interference generation. We present a prototype implementation of a scrambled coding for secrecy mechanisms with interference generation by the legitimate receiver and the cancellation of the effect of self-interference (SI). Regarding the SI cancellation, four state-of-the-art algorithms were considered: Least mean square (LMS), normalized least mean square (NLMS), recursive least squares (RLS) and QR decomposition recursive least squares (QRDRLS). The prototype implementation is performed in real-world software-defined radio (SDR) devices using GNU-Radio, showing that the LMS outperforms all other algorithms considered (NLMS, RLS and QRDRLS), being the best choice to use in this situation (SI cancellation). It was also shown that it is possible to secure communication using only noise generation by the legitimate receiver, though a variation of the packet loss rate (PLR) and the bit error rate (BER) gaps is observed when moving from the fairest to an advantageous or a disadvantageous scenario. Finally, when noise generation was combined with the adapted scrambled coding for secrecy with a hidden key scheme, a noteworthy security improvement was observed resulting in an increased BER for Eve with minor interference to Bob. 

   more » « less
3. Independent dominating sets in graphs of girth five

   https://doi.org/10.1017/s0963548320000279  

   Harutyunyan, Ararat; Horn, Paul; Verstraete, Jacques (May 2021, Combinatorics, Probability and Computing)

   Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result. 

   more » « less
4. Rapid simulation of two-dimensional spectra with correlated anisotropic dimensions

   https://doi.org/10.1063/5.0200042  

   Srivastava, Deepansh J; Baltisberger, Jay H; Grandinetti, Philip J (April 2024, The Journal of Chemical Physics)

   A new algorithm has been developed to simulate two-dimensional (2D) spectra with correlated anisotropic frequencies faster and more accurately than previous methods. The technique uses finite-element numerical integration on the sphere and an interpolation scheme based on the Alderman–Solum–Grant algorithm. This method is particularly useful for numerical calculations of joint probability distribution functions involving quantities with a parametric orientation dependence. The technique’s efficiency also allows for practical least-squares fitting of experimental 2D solid-state nuclear magnetic resonance (NMR) datasets. The simulation method is illustrated for select 2D NMR methods, and a least-squares analysis is demonstrated in the extraction of paramagnetic shift and quadrupolar coupling tensors and their relative orientation from the experimental shifting-d echo 2H NMR spectrum of a NiCl2 · 2D2O salt. 

   more » « less
5. Algorithmic Thresholds for Refuting Random Polynomial Systems

   https://doi.org/10.1137/1.9781611977073.49  

   Hsieh, Tim; Kothari, Pravesh K. (January 2022, Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   Consider a system of m polynomial equations {pi(x)=bi}i≤m of degree D≥2 in n-dimensional variable x∈ℝn such that each coefficient of every pi and bis are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest m -- the algorithmic threshold -- for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every d∈ℕ, the (n+m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever m≥O(n)⋅(nd)D−1. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all d. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at m≳O˜(n)⋅n(1−δ)(D−1) for 2nδ-time algorithms for all δ. 

   more » « less