More Like this

1. Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling

   Neely, Michael J (January 2017, Proc. Allerton Conference on Communication, Control, and Computing)

   This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a- priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed step- size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing drift-plus-penalty based algorithms. This raises important open questions regarding optimal adaptation. 

   more » « less
2. Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling

   Neely, Michael J. (October 2017, PROC. ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING 2017)

   This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a- priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed step- size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing drift-plus-penalty based algorithms. This raises important open questions regarding optimal adaptation. 

   more » « less
3. Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝

   https://doi.org/10.1145/3564246.3585250  

   Sun, Xiaorui (June 2023, ACM)

   The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $$n$$, an algorithm with $$n^{(\log n + O(1))}$$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $$n^{(1 / 4 + o(1))\log n}$$ running time (Rosenbaum 2013). The isomorphism testing for $$p$$-groups of (nilpotent) class 2 and exponent $$p$$ has been identified as a major barrier to obtaining an $$n^{o(\log n)}$$ time algorithm for the group isomorphism problem. Although the $$p$$-groups of class 2 and exponent $$p$$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $$n^{O(\log n)}$$ running time. In this paper, we present an isomorphism testing algorithm for $$p$$-groups of class 2 and exponent $$p$$ with running time $$n^{O((\log n)^{5/6})}$$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces. 

   more » « less
4. Computation of Cycle Bases in Surface Embedded Graphs

   Fox, Kyle; Stanley, Thomas (December 2022, 33rd International Symposium on Algorithms and Computation)

   Bae, Sang Won; Park, Heejin (Ed.)

   We present an O(n³ g² log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³ n + m² n² log n) applicable to general directed graphs. While an O(n^ω + 2^{2g} n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well. 

   more » « less
5. Search-To-Decision Reductions for Kolmogorov Complexity

   https://doi.org/10.4230/lipics.ccc.2024.34  

   Mazor, Noam; Pass, Rafael (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   {"Abstract":["A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-t program generating a given string x is at most s.\r\nIn this work, we consider the more "robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound s and a running time bound t, the goal is to determine whether there exists a poly(t,|x|)-time program of length s+O(log |x|) that generates x. We present the first non-trivial search-to-decision reduction R for the GapMINKT problem; R has a running-time bound of 2^{ε n} for any ε > 0 and additionally only queries its oracle on "thresholds" s of size s+O(log |x|). As such, we get that any algorithm with running-time (resp. circuit size) 2^{α s} poly(|x|,t,s) for solving GapMINKT (given an instance (x,t,s), yields an algorithm for finding a witness with running-time (resp. circuit size) 2^{(α+ε) s} poly(|x|,t,s).\r\nOur second result is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.\r\nA central component in both of these results is the use of Kolmogorov and Levin’s Symmetry of Information Theorem."]} 

   more » « less