For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((\sigma,\rho)\)-problems and of Bergougnoux and Kant\'e (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korh...
Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing...
It is proved that Block Orthogonality alone forces both Type Partition and the existence of a single Mal'tsev operation preserving all generated support and row-equivalence relations, and the three-condition characterization collapses to Block Orthogonality.
We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and M\"ull...
This work introduces two complementary synthesis-oriented existence-checking methods: a rewrite-based normalization algorithm (RwUn) and a template-based reasoning system (TpUn) that guarantees uncomputation through structured Store-Use patterns.
Bona is presented, the first scheduler for dirty-qubit borrowing, built on a novel depth-aware heuristic algorithm, and it reduces nearly 99% of dirty ancillas on average with controlled depth overhead, providing concrete evidence that dirty ancillas offer unique optimization advantages in circuits with certain paralle...
Xiao-Quan Xu, Chen-Ke Liu, Bo-Ning Meng et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
