Vi studerar en kommunikationsvariant av lokal sökning. Det finns några fasta, allmänt kända graf G. Alice håller f A och Bob håller f B, båda är funktioner som anger ett värde för varje vertex. Målet är att hitta en lokal maximum av f A + f B med avseende på G, d.v.s. en vertex v för vilken (Vårt huvudsakliga resultat är att hitta en lokal maximum kräver polynom (i antalet hörn) bitar av kommunikation. Resultatet innehåller följande grupper av grafer: tredimensionella rutnät, hyperkuber, udda grafer och grad 4 grafer. Dessutom visar vi oss vara en optimal kommunikation som är bunden till  och för hyperkuben, och för ett rutnät med konstant dimension, där N är antalet hörn i grafen. Vi tillhandahåller applikationer av vårt huvudresultat i två domäner, exakta potentiella spel och kombinatoriska auktioner. Vart och ett av resultaten visar en exponentiell separation mellan den icke-deterministiska kommunikations komplexiteten och den randomiserade kommunikations komplexiteten i ett totalt sökproblem. För det första visar vi att hitta en ren Nash jämvikt i 2-player N -action exakt potentiella spel kräver poly (N ) kommunikation. Vi visar också att hitta en ren Nash jämvikt i n-player 2-åtgärd exakt potentiella spel kräver exp(n) kommunikation. Den andra domänen som vi anser är kombinatoriska auktioner, där vi bevisar att hitta ett lokalt maximum i kombinatoriska auktioner kräver exponentiellt (i antalet objekt) kommunikation även när värderingarna är submodulära. • Teori om beräkning → Kommunikation komplexitet; Exakt och ungefärlig beräkning av jämvikt.
Babichenko m.fl. REF bevisar kommunikation komplexitet lägre gränser för att hitta en ren jämvikt i den begränsade klassen av potentiella spel.
The communication complexity of local search
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}