Skip to content
Log in
#edge computing

Efficient Minimum $k$-Truss Search: A Decomposition-Based Approach

Qifan Zhang Yang Liu Kaiqiang Yu Shengxin Liu Cheng Long Xun Zhou
Sep 2026 · IEEE Transactions on Knowledge and Data Engineering · Vol 38, pp. 5811-5825 · 0 citations · 69 references

Abstract

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq3-3701433.gif"/></alternatives></inline-formula>-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq4-3701433.gif"/></alternatives></inline-formula>-truss problem aims to find the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq5-3701433.gif"/></alternatives></inline-formula>-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq6-3701433.gif"/></alternatives></inline-formula>-truss, we consider a novel problem called the <italic>minimum <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq7-3701433.gif"/></alternatives></inline-formula>-truss problem</italic>, which seeks to identify a <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq8-3701433.gif"/></alternatives></inline-formula>-truss with the minimum number of vertices, where <inline-formula><tex-math notation="LaTeX">$k\geq 2$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="yu-ieq9-3701433.gif"/></alternatives></inline-formula> is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithm <monospace>MTEnum</monospace> that is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts, <monospace>MTEnum</monospace> still faces practical efficiency issues which may be due to the fact that the <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq10-3701433.gif"/></alternatives></inline-formula>-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based framework <monospace>DSA</monospace>, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model called <italic>edge-based <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq11-3701433.gif"/></alternatives></inline-formula>-plex (<inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq12-3701433.gif"/></alternatives></inline-formula>-eplex)</italic>. With the hereditary property of <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives><mml:math><mml:mi>s</mml:mi></mml:math><inline-graphic xlink:href="yu-ieq13-3701433.gif"/></alternatives></inline-formula>-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithm <monospace>DSA</monospace>. In particular, <monospace>DSA</monospace> runs up to five orders of magnitude faster than the baseline <monospace>MTEnum</monospace>.

DOI Semantic Scholar
View source

Similar papers

Open access 2026

On the k-Total Domination Number of Circulant, Shadow, and Strong Product Graphs

A set <inline-formula> <tex-math notation="LaTeX">$S\subseteq V(G)$ </tex-math></inline-formula> is called a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating set of a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> if every vertex of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> lies within distance at most <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> of some other vertex in <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$k\ge 1$ </tex-math></inline-formula>. The minimum cardinality of such a set is called the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, denoted by <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula>. In this paper, we investigate <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination from a coverage-based perspective. We establish a new lower bound for <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula> in terms of the diameter of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. To analyze neighborhood coverage in <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination, we extend the concepts of shadow and share to <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and introduce the neighborhood coverage number. We also extend the concept of redundant domination to the setting of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods. Together, these concepts quantify both the coverage provided by <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and the overlap among them. These concepts yield new insights into the structure of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating sets and are applied to obtain results for circulant graphs. We show that the shadow graph operation preserves the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number; that is, <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(D_{2}(G))=\gamma _{t,k}(G)$ </tex-math></inline-formula> for every graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. For strong product graphs, we establish general upper bounds and prove that <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(H\boxtimes H')=\gamma _{t,k}(H)$ </tex-math></inline-formula> whenever <inline-formula> <tex-math notation="LaTeX">$r(H')\le k$ </tex-math></inline-formula>. As a consequence, we obtain exact values of the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number for several classes of shadow and strong product graphs, including shadow graphs of paths and cycles, and strong products of paths and cycles.

N. Eswar, R. Jayagopal · 0 citations
Review Open access Jul 2026

Analyzing lexicographical linear inequality systems via convex hulls

<jats:p> Lexicographical extensions of well-known separation theorems for convex sets in <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> are provided in the literature. Particularly, recent theorems regarding open and closed separation of a convex set from any outside point by linear operators from <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> to <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> , in the sense of the lexicographical order of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>m</mml:mi> </mml:msup> </mml:math> </jats:alternatives> </jats:inline-formula> , for each <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$m\in \{1,\ldots ,n\}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> , allow to define two new families of properties for convex sets. Based on these results, that we review and extend in this paper, we provide dual characterizations for the consistency of two kinds of systems defined by weak and/or strict lexicographical linear inequalities, and for those inequalities which are satisfied for every solution of a given system. Such results are formulated in terms of appropriate convex hulls of certain sets depending on the coefficients of the system. </jats:p>

J. Vicente-Pérez, Margarita M. L. Rodríguez · 0 citations
Open access Aug 2026

Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

<jats:p> Seymour’s second neighborhood conjecture states that every oriented graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> </jats:alternatives> </jats:inline-formula> has a Seymour vertex, namely, <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> </jats:alternatives> </jats:inline-formula> has a vertex whose second-order out-neighborhood is at least as large as its first-order out-neighborhood. In this paper, we approach the conjecture by considering an inhomogeneous random graph <jats:italic>G</jats:italic> , where each edge <jats:italic>e</jats:italic> in the complete graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$K_n$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> </jats:alternatives> </jats:inline-formula> appears independently with probability <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$p_n(e)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> . Under suitable density and regularity conditions, we show that every orientation of <jats:italic>G</jats:italic> contains a Seymour vertex with high probability, confirming the conjecture asymptotically. Moreover, if we consider an inhomogeneous random oriented graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> </jats:alternatives> </jats:inline-formula> by assigning an orientation to each edge of <jats:italic>G</jats:italic> independently with equal probability, we prove that <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> </jats:alternatives> </jats:inline-formula> contains a Seymour vertex with high probability across a broader range of regimes. </jats:p>

Y. Shang · 0 citations
Open access Jul 2026

Generalised Hardness of Approximation and the SCI Hierarchy –On Determining the Boundaries of Training Algorithms in AI

<jats:p> Generalised hardness of approximation (GHA) is the phenomenon that one can easily compute an <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\epsilon $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> </jats:alternatives> </jats:inline-formula> -approximation to a solution of a computational problem for <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\epsilon> \epsilon _1 > 0$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> , but for <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\epsilon < \epsilon _1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo><</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> (the approximation threshold) it suddenly becomes hard, for example, non-computable or intractable (non-polynomial time). In this paper we demonstrate the phenomenon that GHA happens when using AI techniques for solving inverse problems, namely training neural networks (NNs) to optimally perform on the training data. In particular, for any non-zero underdetermined linear inverse problem the following phase transition can occur: For a certain family of training sets <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\Omega $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Ω</mml:mi> </mml:math> </jats:alternatives> </jats:inline-formula> , one can prove the existence of optimal NNs for solving the inverse problem for each <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\mathcal {T}\in \Omega $$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>Ω</mml:mi> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> , however, these optimal neural networks can only be computed to a certain accuracy <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\epsilon _1 > 0$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> . Below the approximation threshold <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\epsilon _1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> </jats:alternatives> </jats:inline-formula> , not only does it become intractable to compute the NNs, it becomes impossible regardless of computing power, and no randomised algorithm can solve the problem with probability better than 1/2. Moreover, despite the existence of a stable optimal NN, any attempts of computing it below two times the approximation threshold <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$2\epsilon _1$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> will yield an unstable NN. Our results use and extend the current mathematical framework of the Solvability Complexity Index (SCI) hierarchy and initiate a program for analysing the GHA phenomenon throughout computational mathematics and AI. GHA generalises the phenomenon of hardness of approximation in discrete computations to arbitrary computational problems. </jats:p>

Luca Eva Gazdag, Alexander Bastounis, Anders C. Hansen · 0 citations
2026

Complex Relational Community Search in Heterogeneous Information Networks

Community search in heterogeneous information networks (HINs) is a fundamental task in graph management and analysis. Existing relational community search models, which rely on simple connection requirements between vertices, often fall short of capturing users’ complex needs. To address this limitation, we introduce the concept of <italic>complex relational constraints based on meta-paths</italic>. These constraints enable users to specify refined connection requirements by limiting the number of meta-paths between vertex pairs, thereby capturing higher-order semantic relationships. Based on this, we formally define the complex relational community and formulate the problem of <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula>inimum <inline-formula> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula>omplex <inline-formula> <tex-math notation="LaTeX">$R$ </tex-math></inline-formula>elational <inline-formula> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula>ommunity <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>earch (<italic>MCRCS</italic>), which identifies the minimal such community containing a given query vertex, and prove its NP-hardness. To solve the MCRCS problem, we propose both exact and approximate algorithms. We first develop two exact algorithms: a global vertex-removal method (<italic>Global</italic>) and a local search method (<italic>Ls</italic>). Given the problem’s complexity, we then introduce two efficient approximation algorithms, <italic>Greedy</italic> and <italic>LsApp</italic>, which employ vertex prioritization strategies to find high-quality communities with significantly reduced computational cost. Comprehensive experiments on four real-world HIN datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

Chuanyu Zong, Ziyi Cai, Tao Qiu et al. · 0 citations
Open access Aug 2026

Effective bounds on characterising slopes for all knots

<p> A slope <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p slash q"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p/q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is characterising for a knot <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K subset-of double-struck upper S cubed"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo> ⊂ </mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">S</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">K \subset \mathbb {S}^3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if the orientation-preserving homeomorphism type of the manifold <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper S Subscript upper K Superscript 3 Baseline left-parenthesis p slash q right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">S</mml:mi> </mml:mrow> <mml:mi>K</mml:mi> <mml:mn>3</mml:mn> </mml:msubsup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {S}^3_K(p/q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> obtained by performing Dehn surgery of slope <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p slash q"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p/q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> along <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> uniquely determines the knot <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We combine new applications of results from hyperbolic geometry with previous individual work of the authors to determine, for any given knot <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , an explicit bound <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper C left-parenthesis upper K right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">C</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {C}(K)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue q EndAbsoluteValue greater-than script upper C left-parenthesis upper K right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>q</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">C</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">|q| > \mathcal {C}(K)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> implies that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p slash q"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p/q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a characterising slope for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Furthermore, we find an optimal such <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper C left-parenthesis upper K right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">C</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi>

Patricia Sorya, L. Wakelin · 0 citations

Related blog posts

Microsoft Research Blog Aug 31, 2026

GigaPath-Flash and GigaTIME-Flash: Toward population-scale discovery with efficient pathology foundation models

What if pathology foundation models could do more with less? GigaPath-Flash and GigaTIME-Flash cut computational demands while maintaining strong performance, opening the door to larger studies and broader exploration. The post GigaPath-Flash and GigaTIME-Flash: Toward population-scale discovery with efficient pathology foundation models appeared first on Microsoft Research.

MIT News · Artificial Intelligence Aug 27, 2026

Looking beyond natural sequences

A new machine-learning framework aims to improve the success rate of computational protein design while moving away from results that reproduce sequences found in nature.