Numero

Veckobladet om forskning,
undervisning och
administration, m.m.

Nummer 8 · 27 februari 2003 · Årgång 33      
NADA
Seminarium i teoretisk datalogi

(Icke-)approximerbarhet hos
ekvationer över ändliga grupper.

Jonas Holmerin, NADA, KTH.
10 mars, 13.00-14.00, rum 4523.

En ekvation över en ändlig grupp G är ett uttryck på formen w_1 w_2...w_k = 1_G, där varje w_i är en variabel, en inverterad variabel, eller konstant från G. En sådan ekvation är satisfierbar om det går att tilldela variablerna värden från G på ett sådant sätt att likheten realiseras.

I detta seminarium behandlas problemet att samtidigt satisfiera så många som möjligt av en familj av ekvationer över en ändlig grupp G. Vi presenterar ett bevis för att det är NP-svårt att satisfiera mer än en andel 1/|G| av det optimala antalet ekvationer, eller med andra ord att problemet är NP-svårt att approximera inom |G|-epsilon för varje epsilon > 0. Motsvarande resultat var tidigare känt enbart för Abelska grupper (Håstad 2001).

I seminariet skissar vi på en koppling mellan problemet att satisfiera maximalt antal ekvationer och så kallade PCPer ("Probabilistically Checkable Proofs"), som kan ses som ett slags spel mellan två personer, en verifierare och en bevisare, där bevisaren vill övertyga verifieraren om något påstående. Vi konstruerar ett sådant spel som motsvarar optimeringsproblemet ovan, och för att analysera detta spel använder vi sedan representationsteori för ändliga grupper.

Arbetet har utförts tillsammans med Lars Engebretsen och Alexander Russell.
KTHs stipendiefonder
för forskare och forskarstuderande


KTHs resestipendier ur olika fonder för olika kategorier sökande, forskare, lärare och forskarstuderande
Sista ansökningsdag 3 mars 2003.

Översikten över stipendierna finns även som pdf-doku-ment under www.kth.se/aktuellt/stipendier.
Dags att söka
Forskningsbidrag
från Vetenskapsrådet


Ansökningar till Vetenskapsrådet för forskningsbidrag för projekt m m som startar år 2004 skall vara inkomna till Vetenskapsrådet;
• för ansökningar som avser humaniora och samhälls-vetenskap, konstnärligt FoU, genusforskning med inrikt-ning mot teori- och begreppsutveckling senast fredagen den 11 april
• för övriga ansökningar senast fredagen den 25 april

Blankett för elektronisk ansökan och anvisningar kommer att läggas ut på Vetenskapsrådets hemsida www.vr.se måndagen den 3 mars.
Så ska Sveriges
forskning stärkas


Stöd till forskning vid universitet och högskolor med vetenskapsområden - inte till nya särskilda forskningsinstitut, större och långsiktiga rambidrag till de bästa forskargrupperna i den årliga utlysningen av projektmedel samt stöd till forskargrupper i geografiskt samlad samverkan. Detta är några av de åtgärder som Vetenskapsrådet, VR, vill göra för att stärka den svenska universitetsforskningen. Det framgår av en rapport som VR tagit fram på uppdrag av regeringen ioch som presenterades i dag, måndagen 24 februari.

VR vill också skapa incitament till lärosätena att prioritera framväxten av högklassiga forskningsmiljöer vid fördelningen av fakultetsmedel, ge fortsatt stöd genom särskilda medel till unga forskare och utöka uppföljningen av kvaliteten i svensk grundforskning.

Hela rapporten finns att läsa på www.vr.se

KTH-Ekot




Den 1 mars delas Skolverket
i två myndigheter


Den ena kommer även i fortsättningen att heta Skolverket. Den andra blir Myndigheten för skolutveckling.

Nya SKOLVERKETs huvuduppgift blir att granska utbildningens kvalitet och resultat i kommuner och skolor samt utöva tillsyn över verksamheten. Ambitionen är enligt utbildningsminister Thomas Östros att antalet utbildningsinspektioner ska fördubblas. I princip ska varje skolhuvudman och i princip alla skolor besökas regelbundet av Skolverkets inspektörer. Skolverket ska också fortsättningsvis ansvara för information om styrsystemet, för godkännande av fristående skolor och för styrdokumenten.

MYNDIGHETEN FÖR SKOLUTVECKLING ska stödja kommuner, skolor och barnomsorg i arbetet med att förbättra och vidareutveckla sin verksamhet. Den ska också svara för rektorsutbildningen och främja kompetensutveckling av skolans och barnomsorgens medarbetare. Vidare ska den främja och sprida resultat från forskning. Myndigheten för skolutveckling ska både genomföra generella utvecklings-insatser inom skolsystemet och ge riktat stöd till enskilda skolor och kommuner med särskilda behov.

KTH-Ekot
Numero är institutionstidningen vid Nada – institutionen för numerisk analys och datalogi, KTH. Numero utkommer normalt på torsdags-förmiddagar under teminstid. Manus måste lämnas in före kl.12 på onsdagar.Manus, tips, förslag och andra bidrag till Numero kan lämnas på något av följande sätt: Bidrag för artiklar och notiser bör i största möjliga mån vara färdigformulerade och korrekturlästa. Varje Numeronummer utkommer i två former: Numeroredaktionen består av Rickard Buch. Ansvarig utgivare är Ingrid Melinder. Numeros innehåll uttrycker inte institutionens officiella ståndpunkt annat än då detta anges.Ibland refereras till Numeropärmen. Det är en pärm som finns i bokhyllan i Nadas fikarum på plan 4, i vilken kompletterande information sätts in, försett med nummer på formen 03:NN-N.

Kalendarium

Tors. 27 februari kl 15.15 Presentation av exjobb i datalogi och människa-datorinter-aktion. Antoine Solis, Karl Hasselström och Mattias Erneholm.
Rum 4523
Fre. 28 februari kl 10.00 Disputation. Rickard Domeij: Datorstödd språkgranskning under skrivprocessen - Svensk språkkontroll ur användarperspektiv. Hörsal 8, Hus D, Södra huset, Stockholms universitet.
Mån. 10 mars kl. 13.00-14.00 Seminarium i teoretisk datalogi. Jonas Holmerin: (Icke) approximerbarhet hos ekvationer över ändliga grupper. Rum 4523.
Mån. 17 mars kl 15.00-17.00 Ledarskapsseminarium. " Kommunikation". Sal E3.

 

"Always question. Always analyze. But in the end, suspend judgment until you've been there. Live it to learn it."

Mark McClinchie