Yuefeng Du

Yuefeng Du

The Exact Matching problem asks whether a bipartite graph with edges colored red and blue admits a perfect matching with exactly t red edges. Introduced by Papadimitriou and Yannakakis in 1982, the problem has resisted deterministic polynomial-time algorithms for over four decades, despite admitting a randomized solution via the Schwartz-Zippel lemma since 1987. We prove the Affine-Slice Nonvanishing Conjecture (ASNC) for all bipartite braces and give a deterministic O(n^6) algorithm for Exact Matching on all bipartite graphs. The algorithm follows via the tight-cut decomposition, which reduces the decision problem to brace blocks. The proof proceeds by structural induction on McCuaig's brace decomposition. We establish the McCuaig exceptional families, the replacement determinant algebra, and the narrow-extension cases (KA, J3 to D1). For the superfluous-edge step, we introduce two closure tools: a matching-induced Two-extra Hall theorem that resolves the rank-(m-2) branch via projective-collapse contradiction, and a distinguished-state q-circuit lemma that eliminates the rank-(m-1) branch entirely by showing that any minimal dependent set containing the superfluous state forces rank m-2. The entire proof has been formally verified in the Lean 4 proof assistant.

Yuefeng Du, Huayi Duan, Anxin Zhou et al.

How to audit outsourced data in centralized storage like cloud is well-studied, but it is largely under-explored for the rising decentralized storage network (DSN) that bodes well for a billion-dollar market. To realize DSN as a usable service in a truly decentralized manner, the blockchain comes in handy -- to record and verify audit trails in forms of proof of storage, and based on that, to handle fair payments with necessary dispute resolution. Leaving the audit trails on the blockchain offers transparency and fairness, yet it 1) sacrifices privacy, as they may leak information about the data under audit, and 2) overwhelms on-chain resources, as they may be practically large in size and expensive to verify. Prior auditing designs in centralized settings are not directly applicable here. A handful of proposals targeting DSN cannot satisfactorily address these issues either. We present an auditing solution that addresses on-chain privacy and efficiency, from a synergy of homomorphic linear authenticators with polynomial commitments for succinct proofs, and the sigma protocol for provable privacy. The solution results in, per audit, 288-byte proof written to the blockchain, and constant verification cost. It can sustain long-term operation and easily scale to thousands of users on Ethereum.