The frame scaling problem is: given vectors , marginals , and precision ɛ > 0, find left and right scalings such that (v1,…,vn) := (Lu1r1,…, Lunrn) simultaneously satisfies and , up to error ɛ. This problem has appeared in a variety of fields throughout linear algebra and computer science. In this work, we give a strongly polynomial algorithm for frame scaling with log(1/ɛ) convergence. This answers a question of Diakonikolas, Tzamos and Kane (STOC 2023), who gave the first strongly polynomial randomized algorithm with poly(1/ɛ) convergence for Forster transformation, the special case . Our algorithm is deterministic, applies for general marginals , and requires O(n3 log(n/ɛ)) iterations as compared to the O(n5d11/ɛ5) iterations of DTK. By lifting the framework of Linial, Samorodnitsky and Wigderson (Combinatorica 2000) for matrix scaling to the frame setting, we are able to simplify both the algorithm and analysis. Our main technical contribution is to generalize the potential analysis of LSW to the frame setting and compute an update step in strongly polynomial time that achieves geometric progress in each iteration. In fact, we can adapt our results to give an improved analysis of strongly polynomial matrix scaling, reducing the O(n5 log(n/ɛ)) iteration bound of LSW to O(n3 log(n/ɛ)). Additionally, we give a bound on the size of approximate scaling solutions, which involves condition measure studied in the linear programming literature, and may be of independent interest.

We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear convergence. This implies that a simple gradient descent algorithm also has linear convergence under the same assumption. The spectral gap condition for operator scaling is closely related to the notion of quantum expander studied in quantum information theory. The spectral analysis also provides bounds on some important quantities of the scaling problems, such as the condition number of the scaling solution and the capacity of the matrix and operator. These results can be used in various applications of scaling problems, including matrix scaling on expander graphs, permanent lower bounds on random matrices, the Paulsen problem on random frames, and Brascamp--Lieb constants on random operators. In some applications, the inputs of interest satisfy the spectral condition and we prove significantly stronger bounds than the worst case bounds.

Modern System on Chips (SoCs) are becoming increasingly complex with a growing number of CPUs, caches, accelerators, memory and I/O subsystems. For such designs, a packet based distributed networks-on-chip (NoCs) interconnect can provide scalability, performance and efficiency. However, the design of such a NoC involves optimizing a large number of variables such as topology, routing choices, arbitration and quality of service (QoS) policies, buffer sizes, and deadlock avoidance policies. Widely varying die sizes, power, floorplan and performance constraints across a variety of different market segments, ranging from high-end servers to low-end IoT devices, impose additional design challenges. In this paper we demonstrate that there is a strong correlation between SoC characteristics and good NoC design practices. However this correlation is highly non-linear and multidimensional, with dimensions indicative of the features of the SoC, design goals and properties of the NoC. This results in a high-dimensional NoC design space and complex search process which is inefficient to solve with classic algorithms. Using a variety of real SoCs and training data sets, we demonstrate that a machine learning (ML) based approach yields near-optimal NoC designs quickly. We determine a number of SoC and NoC features, describe reduction methods, and also show that a multi-model approach yields better designs. We demonstrate that for a wide variety of SoCs, ML based NoC designs are far superior to those designed and optimized manually over years on almost all quality metrics.

The Paulsen problem is a basic open problem in operator theory: Given vectors u1, …, un ∈ ℝd that are є-nearly satisfying the Parseval’s condition and the equal norm condition, is it close to a set of vectors v1, …, vn ∈ ℝd that exactly satisfy the Parseval’s condition and the equal norm condition? Given u1, …, un, the squared distance (to the set of exact solutions) is defined as infv ∑i=1n || ui − vi ||22 where the infimum is over the set of exact solutions. Previous results show that the squared distance of any є-nearly solution is at most O(poly(d,n,є)) and there are є-nearly solutions with squared distance at least Ω(d є). The fundamental open question is whether the squared distance can be independent of the number of vectors n.

In the sandpile model, we are given an undirected graph G and an initial list of chip counts on each vertex of G and we may fire degree(v) chips from any vertex v to its neighbors. Doing chip moves either results in a unique terminal configuration or recurs forever. On many families of graphs - including trees - the problem of computing the final configuration is P-complete [13] and simulation can take as long as Θ(n3) time. We give a O(n log5 n) time algorithm for trees that computes the terminal configuration or shows that chip firing will not terminate.