Complexitat de la comunicació, complexitat dels circuits i causes comunes (C^2 x C^2 x C^2)

Itinerari

2 setmanes, 3 sessions per setmana, 2 hores per sessió (amb un breu descans)

Dates i hores:

• Dilluns, 3 de novembre de 2025, 15:00–17:15
• Dimecres, 5 de novembre de 2025, 15:00–17:15
• Divendres, 7 de novembre de 2025, 15:00–17:15
• Dilluns, 10 de novembre de 2025, 15:00–17:15
• Dimecres, 12 de novembre de 2025, 15:00–17:15
• Divendres, 14 de novembre de 2025, 15:00–17:15

Ubicació: Les sessions tindran lloc a la sala C3005, situat a Edifici C3 (UPC – Campus Nord).

El problema P vs. NP ha estat qualificat com "un regal de la informàtica per les matemàtiques" pel medallista Fields Steve Smale l'any 2000. També l'any 2000, el problema va ser inclòs com un dels set Problemes del Premi del Mil·lenni del Clay Mathematics Institute. A més de l'elegància intrínseca de la seva formulació matemàtica, la importància del problema P vs. NP rau en les seves profundes implicacions filosòfiques, independentment de com es resolgui. S'espera que l'estudi del problema P vs. NP continuï inspirant nous avenços tecnològics amb un impacte potencial imprevisible en la indústria, les ciències i les perspectives de la IA, més enllà de la impressionant gamma d'èxits ja aconseguits.

Al llarg dels anys des que Steve Cook va formular el problema el 1971, s'han proposat diversos enfocaments per abordar el problema P vs. NP. L'objectiu d'aquest curs és presentar els fonaments, així com alguns dels avenços recents, d'un enfocament combinatori al problema P vs. NP que es va proposar a la dècada de 1980. La idea subjacent de l'enfocament és adoptar una visió abstracta de la computació com una forma limitada de comunicació entre dues parts que, d'una banda, tenen accés limitat a les dades, però de l'altra, gaudeixen de capacitats de computació totpoderoses en compensació. Aquest compromís entre comunicació i computació té l'efecte de convertir les qüestions de computació en problemes purament combinatoris que no depenen de models computacionals i, per tant, són més susceptibles a les eines clàssiques de les matemàtiques.

A la primera part del curs, presentarem el mètode algebraic lineal per demostrar límits inferiors a la complexitat de la comunicació de funcions explícites i, a continuació, discutirem la cèlebre conjectura de rang logarítmic de Lovász i Saks. També demostrarem el límit inferior lineal de Razborov a la complexitat de la comunicació aleatòria del problema de disjunció de conjunts utilitzant les eines modernes de la teoria de la informació. A la segona part del curs, introduirem els jocs de Karchmer-Wigderson, que caracteritzen la complexitat dels circuits booleans en termes de comunicació. La metodologia dels jocs KW s'utilitzarà per demostrar límits inferiors lineals a la profunditat dels circuits booleans monòtons que calculen coincidències màximes en gràfics, i límits inferiors exponencials a la mida dels circuits booleans monòtons que calculen clics màxims o coloracions òptimes.

Setmana 1. Professor: Anup Rao
1. Protocols de comunicació deterministes i aleatoritzats (2 hores)
2. Mètodes de Teoria de Rangs i Informació (2 hores)
3. Complexitat aleatòria de la disjunció (2 hores)

Setmana 2. Professor: Albert Atserias
4. Fórmules, circuits i jocs de Karchmer-Wigderson (2 hores)
5. Límits de profunditat de circuit monòtons a partir de la disjunció (2 hores)
6. Límits de mida de circuit monòton a partir de gira-sols i aixecament (2 hores)

Prerequisites:
Un estudiant que tingui coneixements bàsics de matemàtiques discretes, incloent-hi el recompte elemental i la teoria de la probabilitat (discreta), traurà el màxim profit del curs.

Anup Rao i Amir Yehudayoff.
Complexitat i aplicacions de la comunicació.
Cambridge University Press, 2020.

Stasys Jukna.
Complexitat de funcions booleanes.
Springer, 2012.

Totes les activitats organitzades pel CRM han de complir amb el següent Codi de conducta.

Estem al corrent d'una sèrie d'estafes actuals dirigides als participants en activitats de CRM relacionades amb el registre o les reserves d'allotjament. Si un tercer (per exemple, travellerpoint.org, Conference Committee, Global Travel Experts o Royal Visit) us demana informació sobre la reserva o el pagament, ignoreu-los.

Si us plau recorda:
i) CRM mai utilitza tercers per fer la nostra administració d'esdeveniments: els missatges vindran directament del personal de CRM
ii) CRM mai demanarà als participants dades de targeta de crèdit o bancàries
iii) Si teniu qualsevol dubte sobre un correu electrònic que rebeu, poseu-vos en contacte