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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Several works have shown unconditional hardness (via integrality gaps) ofcomputing equilibria using strong hierarchies of convex relaxations. Suchresults however only apply to the problem of computing equilibria that optimizea certain objective function and not to the (arguably more fundamental) task offinding \emph{any} equilibrium.  We present an algorithmic model based on the sum-of-squares (SoS) hierarchythat allows escaping this inherent limitation of integrality gaps. In thismodel, algorithms access the input game only through a relaxed solution to thenatural SoS relaxation for computing equilibria. They can then adaptivelyconstruct a list of candidate solutions and invoke a verification oracle tocheck if any candidate on the list is a solution. This model captures mostwell-studied approximation algorithms such as those for Max-Cut, Sparsest Cut,and Unique-Games.  The state-of-the-art algorithms for computing exact and approximateequilibria in two-player, n-strategy games are captured in this model andrequire that at least one of i) size (~ running time) of the SoS relaxation orii) the size of the list of candidates, be at least $2^{\Omega(n)}$ and$n^{\Omega(\log{(n)})}$ respectively. Our main result shows a lower bound thatmatches these upper bound up to constant factors in the exponent.  This can be interpreted as an unconditional confirmation, in our restrictedalgorithmic framework, of Rubinstein's recent conditional hardness \cite{Rub}for computing approximate equilibria.  Our proof strategy involves constructing a family of games that all share acommon sum-of-squares solution but every (approximate) equilibrium of one gameis far from every (approximate) equilibrium of any other game in the family.

Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium