Siyue Liu

Gérard Cornuéjols, Siyue Liu, R. Ravi

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved. However, the unweighted version conjectured by Woodall remains open. We prove that the Edmonds-Giles conjecture is true if the underlying undirected graph is chordal. We also give a strongly polynomial-time algorithm to construct such a packing.

Di Wu, Siyue Liu, Zixiang Ji et al.

Moderation layers are increasingly a core component of many products built on user- or model-generated content. However, drafting and maintaining domain-specific safety policies remains costly. We present Deep Policy Research (DPR), a minimal agentic system that drafts a full content moderation policy based on only human-written seed domain information. DPR uses a single web search tool and lightweight scaffolding to iteratively propose search queries, distill diverse web sources into policy rules, and organize rules into an indexed document. We evaluate DPR on (1) the OpenAI undesired content benchmark across five domains with two compact reader LLMs and (2) an in-house multimodal advertisement moderation benchmark. DPR consistently outperforms definition-only and in-context learning baselines, and in our end-to-end setting it is competitive with expert-written policy sections in several domains. Moreover, under the same seed specification and evaluation protocol, DPR outperforms a general-purpose deep research system, suggesting that a task-specific, structured research loop can be more effective than generic web research for policy drafting. We release our experiment code at https://github.com/xiaowu0162/deep-policy-research.

Siyue Liu, Olha Silina

Let $\vec{G}=(V,E^+\cup E^-)$ be a bidirected graph whose underlying undirected graph $G=(V,E)$ is $2$-edge-connected. A strongly connected orientation (SCO) is defined as a subset of arcs that contains exactly one of $e^+,e^-$ for every $e\in E$ and induces a strongly connected subgraph of $\vec{G}$. Given a family $\mathcal{F}$ of proper subsets of $V$, we call an SCO tight if there is exactly one arc entering $U$ for every $U\in \mathcal{F}$. We give a polynomial-time algorithm to construct a set $\mathcal{B}$ consisting of tight SCO's which forms an integral basis for the linear hull of tight SCO's. This means that $\mathcal{B}$ is a linearly independent subset of tight SCO's, and every integer vector in the linear hull of tight SCO's can be written as an integral combination of $\mathcal{B}$. This extends the main result of Abdi, Conuéjols, Liu and Silina (IPCO 2025), who gave a non-constructive proof of the existence of such a basis in an equivalent setting. While their proof uses polyhedral theory, our proof is purely combinatorial and yields a polynomial-time algorithm. As an application of our algorithm, we show that parity-constrained tight strongly connected orientation can be solved in deterministic polynomial time. Along the way, we discover appealing connections to the theory of perfect matching lattices.

Niv Buchbinder, Moran Feldman, Siyue Liu et al.

We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exchange systems and $p$-systems. For most of these classes of constraints, our results are the first improvement over what is known to be achievable for adversarial order. For matroids, matching and $p$-matchoids, previous random order results were known, and we improve over some of these as well. In the case of matroids, our improved results show a separation between adversarial and random order semi-streaming algorithms, and exponentially improve the number of passes necessary for getting $1 - 1/e - \varepsilon$ approximation for maximizing a monotone submodular function subject to a matroid constraint. We also prove a new hardness result showing a similar separation for $p$-systems. Our results are based on two new technical tools. One tool provides a general way to translate offline algorithms for many classes of constraints into random order semi-streaming algorithms. The other tool is a semi-streaming variant of a recently proposed offline algorithm for matroid constraints.