More Like this

1. Set Cover in Sub-linear Time

   Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Vakilian, Ali; Yodpinyanee, Anak (January 2018, Annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in [17] to the sub-linear query model, that returns an α-approximate cover using Õ(m(n/k)^1/(α–1) + nk) queries to the input, where k denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of k, the required number of queries is , even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require Ω(nk) queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter k. On the other hand, we show that this bound is not optimal for larger values of the parameter k, as there exists a (1 + ε)-approximation algorithm with Õ(mn/kε^2) queries. We show that this bound is essentially tight for sufficiently small constant ε, by establishing a lower bound of query complexity. Our lower-bound results follow by carefully designing two distributions of instances that are hard to distinguish. In particular, our first lower bound involves a probabilistic construction of a certain set system with a minimum set cover of size αk, with the key property that a small number of “almost uniformly distributed” modifications can reduce the minimum set cover size down to k. Thus, these modifications are not detectable unless a large number of queries are asked. We believe that our probabilistic construction technique might find applications to lower bounds for other combinatorial optimization problems. 

   more » « less
2. Online Prediction in Sub-linear Space

   Peng, Binghui; Zhang, Fred (January 2023, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret o(T) algorithm to T1-α regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary. 

   more » « less
3. Randomized Approximation of Linear Least Squares Regression at Sub-linear Cost

   Pan, Victor Y; Luan, Q. (June 2019, ArXiv.org)
4. ℋ _∞ Optimal Estimation for Linear Coupled PDE Systems

   https://doi.org/10.1109/CDC40024.2019.9029595  

   Das, Amritam; Shivakumar, Sachin; Weiland, Siep; Peet, Matthew M. (December 2019, Proceedings of the IEEE Conference on Decision and Control)
5. IrSi ₃ As ₃ : a first transition metal arsenide non-linear optical material

   https://doi.org/10.1039/D2TA09313H  

   Lee, Shannon J.; Akopov, Georgiy; Adeyemi, Adedoyin N.; Soto, Ernesto; Wu, Kui; Kovnir, Kirill (June 2023, Journal of Materials Chemistry A)

   Noncentrosymmetric (NCS) silicon phosphides have recently shown promise as nonlinear optical materials due to the balance of strong second harmonic generation (SHG) activity and large laser damage threshold (LDT) values. While arsenides of electropositive metals, such as Ba, Mg, Zn, and Cd were explored, no NLO properties for transition metal tetrel arsenides have yet been reported. IrSi 3 As 3 is a novel compound, isostructural to IrSi 3 P 3 , which allows a direct investigation on the impact of the heavier pnictogen on structural and optical properties. The direct bandgap is reduced from 1.8 eV for IrSi 3 P 3 to 1.55 eV for IrSi 3 As 3 . Unlike many NLO chalcogenides, IrSi 3 As 3 has a small bandgap without compromising the balance between SHG signal and high LDT values. IrSi 3 As 3 was found to outperform both its phosphide analogue IrSi 3 P 3 , as well as the state-of-the-art infrared SHG standard AgGaS 2 (AGS) in SHG activity and the LDT. 

   more » « less