Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
AI 速览：作者证明在 Erdős-Rényi 随机图中，寻找大诱导匹配存在尖锐的因子二间隙：简单在线贪心可达约一半最优，而在线算法与低阶多项式算法均无法突破该阈值。
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In $G(n,p)$ with $C/n\le p\le 1-κ$, the largest induced matching has size $(1+o(1))L$ with high probability, where $L=\log_{1/(1-p)}(np)$. A simple online greedy algorithm finds an induced matching of size $(1/2-ε)L$, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size $(1/2+ε)L$ except with probability $\exp(-Ω(L\log(np)))$. In the sparse regime $p=d/n$, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.
Web agents increasingly browse, interpret, and act on web content on behalf of users. In many realistic workflows, however, the visual evidence they consume is not neutral: charts and dashboards can be misleading, shaping judgments without issuing any explicit malicious instruction. Unlike chart question answering, Web Agents treat charts as intermediate evidence whose misinterpretation can propagate into concrete downstream actions --- a reliability risk that remains underexplored. We introduce MisVisAgentBench, the first paired executable benchmark for evaluating how misleading visualizations affect Web Agent execution. It comprises 280 task instances in matched clean--misleading pairs that differ only in chart evidence. We further provide a diagnostic framework that isolates misleading-induced failures from baseline task difficulty and captures execution-level effects such as extra browsing steps and decision hesitation. Across thirteen vision-language Web Agents, replacing clean charts with misleading counterparts reduces the average task success rate by more than 34 percentage points. Moreover, these failures predominantly follow the targeted misleading action branch, suggesting that deceptive charts systematically redirect rather than randomly disrupt agent decisions. These results reveal that visualization robustness is a critical yet understudied dimension of Web Agent safety and reliability.
Visual generation requires both high-level semantic knowledge and fine-grained pixel details. We propose a learning paradigm that assigns these roles to autoregressive pretraining for knowledge acquisition and diffusion post-training for high-fidelity rendering. Within this framework, we study the objective, representation, and scaling of knowledge acquisition and rendering. Controlled comparisons identify autoregression as the stronger pretraining objective for downstream rendering, improving both learning efficiency and final generation quality. We further find that AR-only generation quality does not necessarily correlate with final performance; semantic quality matters more. This motivates a purely semantic tokenizer trained with language supervision alone, without an image decoder or reconstruction loss. We establish compute-optimal scaling laws for knowledge acquisition and rendering, and find that autoregressive pretraining lowers the fitted asymptotic rendering loss compared with pixel diffusion models trained from scratch. Guided by the laws, we train a 3B-parameter text-to-image model with only 6,600 H100 GPU-hours, achieving 86 on GenEval and 87 on DPG-Bench and validating the proposed paradigm at scale.