English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a variation of the problem of corruption detection on networksposed by Alon, Mossel, and Pemantle '15. In this model, each vertex of a graphcan be either truthful or corrupt. Each vertex reports about the types(truthful or corrupt) of all its neighbors to a central agency, where truthfulnodes report the true types they see and corrupt nodes report adversarially.The central agency aggregates these reports and attempts to find a singletruthful node. Inspired by real auditing networks, we pose our problem forarbitrary graphs and consider corruption through a computational lens. Weidentify a key combinatorial parameter of the graph $m(G)$, which is theminimal number of corrupted agents needed to prevent the central agency fromidentifying a single truthful node. We give an efficient (in fact, linear time)algorithm for the central agency to identify a truthful node that is successfulwhenever the number of corrupt nodes is less than $m(G)/2$. On the other hand,we prove that for any constant $\alpha > 1$, it is NP-hard to find a subset ofnodes $S$ in $G$ such that corrupting $S$ prevents the central agency fromfinding one truthful node and $|S| \leq \alpha m(G)$, assuming the Small SetExpansion Hypothesis (Raghavendra and Steurer, STOC '10). We conclude thatbeing corrupt requires being clever, while detecting corruption does not.  Our main technical insight is a relation between the minimum number ofcorrupt nodes required to hide all truthful nodes and a certain notion ofvertex separability for the underlying graph. Additionally, this insight letsus design an efficient algorithm for a corrupt party to decide which graphsrequire the fewest corrupted nodes, up to a multiplicative factor of $O(\logn)$.

Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't