Doktorandseminarier höstterminen 2005 / PhD Student Seminars Autumn Term 2005
- Måndag 10 oktober, kl 13.15-15.00, rum 1537: Optimization of radiation therapy (Fredrik Carlsson, Optimization and Systems Theory, Department of Mathematics, KTH)
-
The goal of external-beam radiation therapy is to obtain an acceptable balance between tumor control and complications to the healthy tissue surrounding the tumor.
In intensity-modulated radiation therapy (IMRT), certain user-specified criteria are given and the optimal settings of the delivery system are sought. This is an ill-conditioned inverse problem, which is discretized and formulated as a large-scale non-linear optimization problem.
My talk will consist of two parts. Firstly, a general formulation of IMRT problems and different aspects of radiation therapy will be discussed. Secondly, techniques for regularizing IMRT problems and suitable optimization methods will be discussed in more detail.
(The talk will be held in Swedish unless there are non-Swedish speakers present.)
-
Måndag 17 oktober, kl 10.15-12.00
(OBS! tiden),
rum 1537:
Execution Time Analysis and Abstract Interpretation
(Björn Lisper,
Department of Computer Science and Electronics, Mälardalen University)
[slides
]
-
Worst-Case Execution Time (WCET) Analysis means to find an upper bound to the longest possible execution time of a piece of software. Such bounds are needed in order to verify the timing correctness in safety-critical real-time systems, where consequences can be fatal if the system does not react within given time limits.
WCET analysis combines elements from both formal program analysis and hardware modelling to achieve its goal. Some current techniques for WCET analysis are based on abstract interpretation, which is a formal framework for program analysis: if a program analysis can be cast in this framework, then correctness comes for free and there is also a generic solution method in the form of fixed-point iteration.
In this talk we will first give describe the basics of WCET analysis and then give an introduction to the theory of abstract interpretation.
(The talk will be held in Swedish unless there are non-Swedish speakers present.)
-
Måndag 24 oktober, kl 13.15, rum 1537:
PCP-satsen på kombinatoriskt manér
(Per Austrin, Teorigruppen, KTH CSC)
[bilder
]
-
Ett PCP (Probabilistically Checkable Proof) för ett påstående (t.ex. att en graf är 3-färgbar) är ett bevis sådant att vi genom att bara kolla på en liten del av beviset med god sannolikhet kan avgöra huruvida det är korrekt.
Den hyllade PCP-satsen från början av 1990-talet säger att ett språk ligger i NP om och endast om det har polynomiellt långa PCP i vilka vi bara behöver läsa ett konstant antal bitar. Sedan dess upptäckt har den varit ett viktigt verktyg inom komplexitetsteorin, med tillämpningar inom bl.a. kodteori och (icke-)approximerbarhet. Jag kommer att prata om en artikel av Dinur från i våras, i vilket hon ger ett rent kombinatoriskt bevis av PCP-satsen.
Man behöver inte vara bekant med PCP sedan tidigare, även om det säkert underlättar. Alla talar svenska. Seminariet kommer preliminärt att vara 2 x 45 minuter.
-
Måndag 31 oktober, kl 10.15-11.00
(OBS! tiden),
rum 1537:
Trusted Platform Modules and Hardware-based Security
(Andreas Nilsson)
[slides
]
-
A growing problem in today's computing environments is security, or lack of security. An effort to make computer platforms more reliable has been made by the Trusted Computing Group in specifying a platform agnostic microcontroller to act as a base for platform integrity. The microcontroller is called a Trusted Platform Module (TPM) and has gained a lot of attention for the ability to enforce so called Digital Rights Management (copy control of downloaded media).
The aim is to present the TPM technology and discuss cryptographic issues around its application, including possible security problems and loss of personal integrity. Both the Trusted Computing Group and its opponents have a rather subjective view on the issues at hand which creates a need for an objective discussion.
The talk will be held in Swedish or English depending on the participants.
-
Måndag 7 november, kl 13.15, rum 1537:
NSA – Non Standard Analysis. En kort introduktion.
(Johan Karlander, Teorigruppen, KTH CSC)
[föreläsningsstolpar
]
-
NSA är en teknik att beskriva matematisk analys på som skiljer sig från de vanliga framställningssätten. Kortfattat handlar tekniken om att ersätta gränsvärdesresonemang med räknande med idealiserade infinitesimal tal eller s.k. hyperreella tal. Detta sätt att tänka var det som Lebniz använde i sin framställning av infinitesimalkalkylen men som sedan föll i glömska tills Abraham Robinson på 1960-talet gjorde en modern, logisk strikt, presentation av metoden.
Jag kommer att tala en del om den logiska bakgrunden till tekniken och sedan ge exempel på hur den kan tillämpas. Jag kommer att fokusera på resultat som har kopplingar till algoritmer. NSA ger ett naturligt samband mellan kontinuerliga mängder och diskreta mängder, t.o.m. ändliga mängder. Integraler kan t.ex. ses som logiskt ekvivalenta med ändliga summor och problemet att hitta maximum till en kontinuerlig funktion är logiskt ekvivalent med att hitta det största talet i en ändlig lista med tal. Denna ekvivalens bygger på att begreppet ändlig har en "ny" tolkning.
En intressant fråga är om NSA skulle kunna vara användbar inom algoritmteori. Det verkar som om det finns flera problem att fundera kring här. I mån av tid kommer jag att diskutera ett resultat av Tennenbaum som säger att alla modeller av NSA nödvändigtvis är icke-rekursiva.
Seminariet kommer preliminärt att vara 2 x 45 minuter.
-
Måndag 14 november, kl 13.15, rum 1537:
Talkroppssållet
(Lina Mårtensson)
[bilder
]
-
Talkroppssållet är den snabbaste kända algoritmen för att faktorisera heltal med fler siffror än 130 som saknar små primtalsfaktorer. I maj slogs ett nytt rekord då ett 200-siffrigt tal faktoriserades.
Jag kommer först att berätta om några av föregångarna till algoritmen, därefter kommer en översiktlig bild av talkroppssållet att ges. Gemensamt för algoritmerna är att man, för att faktorisera ett tal N, vill hitta två heltal x och y sådana att x2 ≡ y2 mod N. Då är chansen mer än 1/2 att gcd(x ± y, N) är en icketrivial faktor till N.
Seminariet kommer att hållas på svenska.
- Måndag 21 november, kl 13.15, rum 1537: Vikten av vikter i tröskelkretsar (Mikael Goldmann, Teorigruppen, KTH CSC)
-
Inom kretskomplexitet är tröskelkretsar med konstant djup en av de enklaste naturliga klasser vars beräkningskapacitet man vet ganska lite om. Varje grind i en tröskelkrets beräknar en viktad summa av sina indata och beroende på om summan är större eller mindre än något tröskelvärde matar grinden ut 1 eller 0.
Hur stora vikter behövs? Under seminariet kommer vi att titta på några av de undre gränser som finns för tröskelkretsar med mycket begränsat djup. Huvuddelen av seminariet kommer dock att handla om ett resultat som visar att stora vikter inte tillför så oerhört mycket: man kan eliminera behovet av stora vikter i en tröskelkrets till priset av att djupet ökar med en nivå och storleken ökar polynomiskt.
- Måndag 5 december, kl 13.15, rum 1537: Sumbers (Fredrik Niemelä, Teorigruppen, KTH CSC)
-
Inom kombinatorisk spelteori beskrivs spel rekursivt som par av mängder av spel. I allmänhet är det svårt att avgöra resultatet av ett spel men det finns delgrupper som har följande trevliga egenskaper:
- Det finns en enkel regel som avgör resultatet vid optimalt spel.
- Det finns en förenklingsregel.
Jag tänkte prata om sumbers som är ytterligare en delgrupp med dessa egenskaper, samt om några spel som kan lösas med hjälp av detta.
-
Onsdag 21 december, kl 15.15 (OBS! dag och tid),
rum 1537:
Dataintegritet i filsystem
(Björn Lalin)
[slides
]
-
Vilka olika metoder finns för att garantera integritet av data i filsystem? Mitt exjobb går ut på att undersöka och jämföra några sådana metoder för användning i ett "nätverkat" filsystem.
Jag planerar att beskriva ett par olika metoder för att ge en överblick av hur detta kan lösas. Specifikt planerar jag att beskriva:
- någon naiv ansats,
- Merkles hashträd,
- hybridmetod av hashträd och inkrementell hashfunktion,
- eventuellt en ansats baserad på entropi av data om tiden räcker till.
Seminariet kommer preliminärt att vara 45-60 minuter långt.