Upp till webbsidan för doktorandseminarierna.
Ett mixnät är en flerpartsberäkning som syftar till att åstadkomma anonymitet. En lista med krypterade meddelanden ges som indata till en grupp servrar. Tillsammans dekrypterar de meddelandena, men blandar under detta också deras ordning. Det man vill åstadkomma är ett mixnät som främst är säkert (hur meddelandena blandas under dekrypteringen skall vara okänt för alla enskilda aktörer), robust (om en delmängd av mix-servrarna fuskar skall detta ej påverka slutresultatet), men även effektivitet är förstås ett viktigt mål. Mixnät är en trevlig byggsten när man gör elektroniska valsystem.
Golle, Zhong, Boneh, Jakobsson och Juels presenterade på Asiacrypt 2002 ett mixnät "Optimistic Mixing for Exit-Polls" som är dubbelt så snabbt som det tidigare snabbast kända mixnätet. Jag beskriver tre fullt praktiska attacker, och knäcker både anonymitet och robusthet hos konstruktionen.
Flyttat till 5 maj p.g.a. akut röstbrist.
Under seminariet visar vi att Tree Alignment ar NP-svårt och ger en PTAS (ej mitt resultat) för problemet.
Tree Alignment: Antag att vi är givna en mängd arter, representerade med DNA-strängar, och ett phylogentiskt träd som beskriver släktskapet hos deras förfäder. Då är Tree Alignment-problemet att hitta DNA-strängar som representerar de förfäder som med så få mutationer som möjligt inducerar de givna arterna enligt trädet. Mutationer är typiskt substitutioner, insättning och bortagning av symboler i strängarna.
Jag kommer att behandla min implementation av schackdatorn Rainman och prata lite allmänt om trädsökning: minimaxing, alpha-beta, transpositionstabeller, dragsortering samt lite om heuristiker såsom sökutvidgningar och nulldrag. Bakgrundsinformation finns på http://www.xs4all.nl/~verhelst/chess/search.html.
Många PCPer analyseras enkelt och behändigt med hjälp av den diskreta Fouriertransformen. Alla har tyvärr inte insett denna metods lättfattlighet och elegans, och djupa suckar kan ibland höras när maskineriet dras igång.
En mer kombinatorisk metod att analysera PCPer har introducerats av Dinur och Safra ("The importance of being biased", STOC 2002). Deras ursprungliga artikel är dock ganska svårläst, så vi kommer att titta på en lättare tillämpning av några av idéerna och visa en undregräns för approximerbarheten av hörntäckning på hypergrafer.
Referenser:
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2001/TR01-104/index.html
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2002/TR02-027/index.html
På allmän begäran bjuder Jonas på en fortsättning av seminariet den 31 mars om kombinatoriska metoder att analysera probabilistiska bevis. Fortsättningsseminariet är baserat på artikeln A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover av Dinur, Guruswami, Khot och Regev.
Den bästa approximationsalgoritmen för asymmetrisk TSP konstruerades 1982 och approximerar i O(log n). Jag har tagit fram en familj av grafer där algoritmen visar ett värsta-fall-beteende. Man får en TSP-tur som är mer än logn/(2+2t) gånger den optimala turen och där t är ett godtyckligt litet tal. Just nu filar jag på en artikel om graferna och vill gärna få feed-back!
Läs manuskriptet på
http://www.nada.kth.se/~annap/paper/worstCase.ps.
In this seminar [continued from the official TCS seminar on April 28th, 2003] we continue to present Bird-Meertens Formalism, a mathematical tool for the construction of generic (datatype-parametric) functional programs. We define further notions of basic category theory: F-algebra and initial F-algebras. We emphasise the role of F-algebras in the represention of recursive (polymorphic) datatypes as functors. We define catamorphism and map.
The seminar will be approximately one hour long and will be held in English.
Ett fundamentalt problem inom den teoretiska datalogin är olika typer av slumpvandringar på grafer. Man tänker sig då en kula som flyttar sig mellan noderna i en graf enligt vissa probabilistiska regler och studerar sannolikheten att kulan befinner sig vid en viss nod efter ett viss antal förflyttningar.
En av de vanligaste frågeställningarna är ungefär som följer: Om man startar i en godtycklig nod och i varje tidssteg går till en slumpmässigt vald granne, hur fort konvergerar fördelningen mot likformig fördelning på alla noderna? Det visar sig att det går relativt enkelt att visa explicita gränser i detta fall om man använder verktyg från harmonisk analys. Vi kommer att presentera dessa verktyg och sedan använda dem för att formulera en lösning på ovanstående slumpvandringsproblem då grafen i fråga är en ring.
Upp till webbsidan för doktorandseminarierna.