We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.
Zhiheng Li, Zongyang Ma, Jiaxian Chen, Cheng Cui, Yi Liu, Ziqi Zhang, Chunfeng Yuan, Bing Li 等 10 位作者
Optical Character Recognition (OCR) is among the oldest and most widely deployed applications of artificial intelligence. This survey reviews its development, focusing on the Foundation Model Era. We define OCR through faithful transcription: within a specified visual scope, OCR should completely reconstruct the text, notation, and document structure observable in the source image, and every textual, notational, or structural element in the output must be verifiable from visual evidence in that image. We trace the development from specialist OCR models toward unified models, examining joint text detection and recognition, structured sequence generation, and the use of pretrained vision-language models (VLMs). We organize contemporary OCR systems into five coexisting families: modular toolkits and task-specific models, specialized document VLMs, hybrid workflows, general-purpose VLMs, and commercial products and managed services. We compare their architectures, data, and training, examining hallucination and omission, insufficient spatial grounding, and inference cost in generative OCR. We review evaluation from character and scene text recognition to parsing individual structural elements and full-page transcription, highlighting gaps in consistent output definitions, attribution of performance to individual components, and coverage of real capture conditions and visible content and structure. Finally, we summarize the challenges facing OCR and discuss directions for future research. We continuously track related work at https://github.com/zhihengli-casia/Awesome-OCR-in-the-Foundation-Model-Era.
We study online Wasserstein distributionally robust optimization (DRO), where the ambiguity set is a Wasserstein ball centered at the empirical distribution and evolves with each observation. We formulate each round as a zero-sum game and develop an online distributional best-response algorithm that requires only one projected subgradient step per iteration. Combining regret analysis with measure concentration, we establish explicit, instance-dependent, and high-probability convergence rates to the optimal offline DRO value.