Bimine and network algorithms

Lecturer : 
Hannu Toivonen
Event type: 
HIIT seminar
Event time: 
2011-05-16 11:00 to 11:30
Place: 
Innopoli2, B317

The Random K-SAT Problem: Solution Space Transitions and Random Walk Heuristics

Lecturer : 
Haijun Zhou
Event type: 
HIIT seminar
Event time: 
2011-05-13 10:15 to 11:00
Place: 
Kumpula Exactum C222
Description: 

Talk announcement:
HIIT Seminar Kumpula, Friday May 13 10:15, Exactum C222

SPEAKER:
Prof. Haijun Zhou
Chinese Academy of Sciences

TITLE:
The Random K-SAT Problem: Solution Space Transitions and Random Walk
Heuristics

ABSTRACT:
                        
The random K-satisfiability problem is an important problem for
studying typical-case complexity of NP-complete combinatorial
satisfaction.  We review recent efforts on the solution space fine
structures of the random K-SAT problem.  A heterogeneity transition is
predicted to occur in the solution space as the constraint density
alpha reaches a critical value alpha_{cm}. This transition marks the
emergency of exponentially many solution communities in the solution
space.  After the heterogeneity transition the solution space is still
ergodic until alpha reaches a larger threshold value alpha_d, at which
the solution communities disconnect from each other to become
different solution clusters (ergodicity-breaking).

The existence of solution communities in the solution space is
confirmed by numerical simulations of solution space random walking.
The performance of a simple random walk search algorithm, SEQSAT, is
also investigated.  This algorithm is very efficient for random 3-SAT,
but for random K>4-SAT instances, the search is blocked as alpha
approaches alpha_d from below.

BIO:

Haijun Zhou is a research professor at the Institute of Theoretical
Physics, Chinese Academy of Sciences.  He works in the area of
statistical physics and its interdisciplinary applications (spin
glasses, complex networks, and polymer physics). He was an invited
speaker at STATPHYS-24 (Austrialia, 2010), and now serves as an

editorial board member for the Journal of Statistical Mechanics.


Welcome!
 

Computationally Supported Collective Science (CS^2)

Lecturer : 
Antti Honkela, Antti Oulasvirta, and Samuel Kaski
Event type: 
HIIT seminar
Event time: 
2011-04-18 13:15 to 14:00
Place: 
Innopoli 2 C432

Computationally Supported Collective Science (CS^2)

Lecturer : 
Samuel Kaski, Antti Honkela, and Antti Oulasvirta
Event type: 
HIIT seminar
Event time: 
2011-04-15 10:15 to 11:00
Place: 
Kumpula Exactum C222
Description: 

This is an internal HIIT event.

All HIIT and UH-CS personnel are warmly welcome to attend.

Probabilistic Models for Alignment of Etymological Data

Lecturer : 
Roman Yangarber
Event type: 
HIIT seminar
Event time: 
2011-04-08 10:15 to 11:00
Place: 
Kumpula Exactum C222
Description: 
Talk announcement:
HIIT Seminar Kumpula, Friday April 8, 10:15, Exactum C222

SPEAKER:
Roman Yangarber
University of Helsinki

TITLE:
Probabilistic Models for Alignment of Etymological Data 

ABSTRACT:
Etymology is the study of origins of words and
relationships and connections among languages.  It involves
many sub-problems, including finding cognates or sets of
genetically related words across a language family,
discovering rules of regular sound correspondence among
the languages, building phylogenetic trees, and
reconstructing hidden data, including proto-languages.  We
focus mainly on the regularity of sound correspondence,
but address some of the others as well.  Our models try to
align etymological data, or find the best alignment at the
sound level, given a set of etymological data.  We aim to
devise methods that are as objective as possible, making
no a priori assumptions---e.g., no preference for
vowel-vowel or consonant-consonant alignments.  One of the
goals is to measure the quality of the data sets, in terms
of their internal consistency.  We introduce a MDL-based
initial model and present several extensions.  We also
discuss several ways for evaluating the results,
qualitatively and quantitatively.  The models are
evaluated on data from the Uralic family (which includes
Finnish, Estonian and Hungarian, among other languages).

(Work done under Academy Project Uralink.
Joint work with Hannes Wettig.)


Welcome!
--Matti Järvisalo

HIIT SEMINAR KUMPULA TENTATIVE SCHEDULE Spring 2011
---------------------------------------------------
Apr  8: Roman Yangarber
Apr 15: * Internal HIIT event* 
Apr 22: * No seminar -- Good Friday *
Apr 29: Antti Oulasvirta / Teemu Roos
May  6: Jesper Nederlof
May 13: Haijun Zhou
May 20: *** free ***
May 27: *** free ***

Pages