Bun M, Juvekar M
The sign rank of a ± 1-valued matrix A is the minimum rank of a real matrix that agrees with A entrywise in sign.The sign rank of a ± 1-valued matrix A is the minimum rank of a real matrix that agrees with A entrywise in sign. For every sufficiently large d, we give an explicit matrix A with 2^(Θ(d^2)) rows and columns and sign rank Θ(d)…
Ding P
Label-free reinforcement learning with verifiable rewards (RLVR) rewards a language model for agreeing with its own majority vote.Label-free reinforcement learning with verifiable rewards (RLVR) rewards a language model for agreeing with its own majority vote. It improves reasoning at first but eventually collapses: the self-assessed reward goes to one while…
Dongmo V, Ninyim AMF
Multi-relational graph detectors learn from clean data how much to trust each relation, but an adversary pays a different price to manipulate each relation and each…Multi-relational graph detectors learn from clean data how much to trust each relation, but an adversary pays a different price to manipulate each relation and each action; taking such costs as given, we ask when using a relation…
Zhu W, Zuo M, Sun H
Audit-based certification bounds the violation rate of an LLM agent by auditing a random fraction ε of actions and reweighting the audited labels; its validity is meant…Audit-based certification bounds the violation rate of an LLM agent by auditing a random fraction ε of actions and reweighting the audited labels; its validity is meant to rest only on the defender's audit coin.
Yang Z, Kumar R, Kroer C
We consider T repeated second-price auctions across n pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve…We consider T repeated second-price auctions across n pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective…
Liu YP, Naidu K, Nguyen HA et al.
We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model.We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model.
Liu S, Li Z, Li B
In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast…In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings.
Adesso G, Lami L, Giovannetti V
The classical capacity of a noisy optical channel is the maximum rate at which information can be transmitted reliably, given a constraint on the mean input energy.The classical capacity of a noisy optical channel is the maximum rate at which information can be transmitted reliably, given a constraint on the mean input energy.
Raskhodnikova S, Smith A, Wagaman C et al.
We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees…We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks.
Bruno R, Vaccaro U
Given a joint distribution PXY on a finite alphabet, the information bottleneck method seeks a representation T of X that is as informative as possible about Y while…Given a joint distribution PXY on a finite alphabet, the information bottleneck method seeks a representation T of X that is as informative as possible about Y while compressing X, where T and Y are conditionally independent given…
Nogler J, Totschnig A, Williams VV
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two…In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and…
Moser BB, Frolov S, Nauen TC et al.
With the rise of large language models, agentic systems are becoming increasingly autonomous, as they write code, call tools, revise prompts, and propose modifications to…With the rise of large language models, agentic systems are becoming increasingly autonomous, as they write code, call tools, revise prompts, and propose modifications to their own components.
Ni Y, Guo Y, Luo J et al.
Kolmogorov-Arnold networks (KANs) have a dimension-independent approximation exponent when the target admits a sufficiently smooth representation by univariate edge…Kolmogorov-Arnold networks (KANs) have a dimension-independent approximation exponent when the target admits a sufficiently smooth representation by univariate edge functions.