Zheng Guo

Tensor network methods provide a scalable solution to represent high-dimensional data. However, their efficacy is often limited by static, expert-defined structures that fail to adapt to evolving data correlations. We address this limitation by formalizing the structural rounding problem for tree tensor networks and introducing a hierarchical search algorithm HiST, which automatically identifies optimized structures with index reshaping for input tree tensor networks. To navigate the combinatorial explosion of the structural search space, HiST integrates stochastic sub-network sampling with hierarchical refinement. This approach utilizes entropy-guided index clustering to reduce dimensionality and targeted reshaping to expose latent data correlations. Numerical experiments on analytical functions and real-world physics applications, including thermal radiation transport, neutron diffusion, and computational fluid dynamics, demonstrate that HiST exhibits empirical polynomial scaling with dimensionality relative to the sampling budget, bypassing the scalability barriers in prior work. HiST achieves compression ratios 2.5x to 100x higher than standard fixed formats such as Tensor Trains and Hierarchical Tuckers (peaking at 1000x). Furthermore, HiST discovers structures that generalize effectively: applying a structure optimized for one data instance to a related target data typically maintains compression performance within 10% of the result obtained by performing structure search on that target data. These results highlight HiST as a robust, automated tool for adaptive data representation and high-dimensional simulation compression with tensor network methods.

Abstract semantics has proven to be instrumental for accelerating search-based program synthesis, by enabling the sound pruning of a set of incorrect programs (without enumerating them). One may expect faster synthesis with increasingly finer-grained abstract semantics. Unfortunately, to the best of our knowledge, this is not the case, yet. The reason is because, as abstraction granularity increases – while fewer programs are enumerated – pruning becomes more costly. This imposes a fundamental limit on the overall synthesis performance, which we aim to address in this work. Our key idea is to introduce an offline presynthesis phase, which consists of two steps. Given a DSL with abstract semantics, the first semantics modeling step constructs a tree automaton A for a space of inputs – such that, for any program P and for any considered input I, A has a run that corresponds to P’s execution on I under abstract semantics. Then, the second step builds an oracle O for A. This O enables fast pruning during synthesis, by allowing us to efficiently find exactly those DSL programs that satisfy a given input-output example under abstract semantics. We have implemented this presynthesis-based synthesis paradigm in a framework, Foresighter. On top of it, we have developed three instantiations for SQL, string transformation, and matrix manipulation. All of them significantly outperform prior work in the respective domains.

Tensor networks provide a powerful framework for compressing multi-dimensional data. The optimal tensor network structure for a given data tensor depends on both data characteristics and specific optimality criteria, making tensor network structure search a challenging problem. Existing solutions typically rely on sampling and compressing numerous candidate structures; these procedures are computationally expensive and therefore limiting for practical applications. We address this challenge by decoupling topology enumeration from rank assignment search. We first represent the search space using canonical dimension trees, a hierarchical structure that encodes potential network topology through nested index partitions. This representation inherently rules out redundant and suboptimal topologies by construction. To mitigate the assessment bottleneck, we introduce a mechanism powered by the precomputation of a singular value map. By archiving the singular values of all feasible tensor matricizations, we transform the evaluation of any candidate dimension tree into a constraint-solving problem. This formulation yields an empirically near-optimal rank assignment via simple metadata lookups, allowing us to compute structural costs directly and bypass expensive on-the-fly tensor decompositions for all but the final selected candidate. Experimental results show that our approach accelerates the structure search by up to 10x while achieving highly competitive compression ratios, outperforming standard tensor trains and hierarchical tuckers by up to 10x, and matching or exceeding state-of-the-art structure search tools. Notably, our approach scales to larger tensors that are unattainable by prior work. Furthermore, the discovered topologies generalize well to similar data; they achieve compression ratios up to 2.4x better than tensor trains or hierarchical tuckers, while maintaining a search time of approximately 110 seconds for 6D tensors of 1-2GB disk size.