More Like this

1. Nearly magic rectangles

   https://doi.org/10.1002/jcd.21667  

   Chai, Feng‐Shun; Singh, Rakhi; Stufken, John (July 2019, Journal of Combinatorial Designs)

   Abstract Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares ismagic rectangleswhich are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by oddnearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist. 

   more » « less
2. Analyticity of Steklov eigenvalues of nearly circular and nearly spherical domains

   https://doi.org/10.1007/s40687-020-0202-4  

   Viator, Robert; Osting, Braxton (March 2020, Research in the Mathematical Sciences)
3. Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

   Ene, Alina; Nguyen, Huy L. (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $$1 - 1/e - \epsilon$$ approximation require $$\Omega(n)$$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $$1 - 1/e - \epsilon$$ approximation using $$O(\ln{n} / \epsilon^2)$$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $$O(n \; \mathrm{poly}(\log{n}, 1/\epsilon))$$. 

   more » « less
4. Testing unateness nearly optimally

   https://doi.org/10.1145/3313276.3316351  

   Chen, Xi; Waingarten, Erik (June 2019, Proceedings of the 51th ACM Symposium on Theory of Computing)
5. Nearly Optimal List Labeling

   https://doi.org/10.1109/FOCS61266.2024.00132  

   Bender, Michael A; Conway, Alex; Farach-Colton, Martín; Komlós, Hanna; Koucký, Michal; Kuszmaul, William; Saks, Michael (October 2024, IEEE)