We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $γ> 1$ such that $\mathsf{CVP}_{p,γ}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,γ}$. Our main contribution is a randomized ETH hardness result for $\mathsf{SVP}_{p,γ}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p \in (2, \infty)$. This result relies on a novel geometric property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm, which says that for any $p \in (2, \infty)$, the number of lattice vectors close to $\frac{1}{2}\vec{1}_n$ (in the $\ell_p$ norm) is exponentially larger than the number of short vectors (namely those close to the origin). We establish this property via a new inequality for the Theta function, which we use to get a randomized reduction from $\mathsf{CVP}_{p,γ}$ to $\mathsf{SVP}_{p,γ'}$. Finally, we also use our ideas to give some minor improvements over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p,α}$ (the Bounded Distance Decoding Problem), yielding better ETH hardness results for $\mathsf{BDD}_{p,α}$ for any $p \in [1, \infty)$ and $α> α_p^{\ddagger}$, where $α_p^{\ddagger}$ is an explicit threshold depending on $p$.

In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.

The finite group isomorphism problem asks to decide whether two finite groups of order$N$are isomorphic. Improving the classical$N^{O(\mathrm{I}\mathrm{o}\mathrm{g}N)}$-time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that$p$groups of class 2 and exponent$p$form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun (STOC '23) presents an$N^{O\left((\log N)^{5 / 6}\right)}$-time algorithm for this group class. In this paper, we improve Sun's algorithm by presenting an$N^{{\tilde{O}}\left((\log {N})^{1^{1 / 2}}\right)}$-time algorithm for this group class. We also extend our result to the more general$p$-groups of Frattini class 2. Our algorithm is obtained by sharpening the key technical ingredients in Sun's algorithm and building connections with other research topics. One intriguing connection is with the maximal and non-commutative ranks of matrix spaces, which have recently received considerable attention in algebraic complexity and computational invariant theory. Results from the theory of Tensor Isomorphism complexity class (Grochow-Qiao, SIAM J. Comput. '23) are utilized to simplify the algorithm and achieve the extension to$p$-groups of Frattini class 2.

Intel CAT is a widely available cache partitioning technique in commercial hardware but falls short in partitioning granularity. We propose LazyCAT, a fine-grained, on-demand, and easy-to-use cache partitioning technique, which not only can ensure the QoS of High-Priority (HP) applications but also yield the under-utilized cache sets to other Best-Effort (BE) applications for better resource efficiency. LazyCAT retains the easy-to-use philosophy of CAT and introduces a new soft LLC partitioning boundary, which is lower than the original CAT partitioning boundary (hard boundary). LazyCAT detects and selects under-utilized cache sets in HP applications during profiling, and specifies them to the soft boundary at runtime dynamically, yielding the cache blocks between these two boundaries for other applications. Meanwhile, LazyCAT provides users with a simple software interface to guide the set-level space allocation according to their needs. Experimental results show that LazyCAT exhibits substantial performance improvements (up to 12.2%) for BE applications with less than 3% performance degradation of HP applications.

We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. Such problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the decision problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problem over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d>3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.

While research has shown that the agile chip design methodology is promising to sustain the scaling of computing performance in a more efficient way, it is still of limited usage in actual applications due to two major obstacles: 1) Lack of tool-chain and developing framework supporting agile chip design, especially for large-scale modern processors. 2) The conventional verification methods are less agile and become a major bottleneck of the entire process. To tackle both issues, we propose MINJIE, an open-source platform supporting agile processor development flow. MINJIE integrates a broad set of tools for logic design, functional verification, performance modelling, pre-silicon validation and debugging for better development efficiency of state-of-the-art processor designs. We demonstrate the usage and effectiveness of MINJIE by building two generations of an open-source superscalar out-of-order RISC-V processor code-named XIANGSHAN using agile methodologies. We quantify the performance of XIANGSHAN using SPEC CPU2006 benchmarks and demonstrate that XIANGSHAN achieves industry-competitive performance.

This paper investigates how to better track and deliver dependency in dependency-based cores to exploit instruction-level parallelism (ILP) as much as possible. To this end, we first propose an analytical performance model for the state-of-art dependency-based core, Forwardflow, and figure out two vital factors affecting its upper bound of performance. Then we propose Omegaflow,a dependency-based architecture adopting three new techniques, which respond to the discovered factors. Experimental results show that Omegaflow improves IPC by 24.6% compared to the state-of-the-art design, approaching the performance of the OoO architecture with an ideal scheduler (94.4%) without increasing the clock cycle and consumes only 8.82% more energy than Forwardflow.