[FOM] [CiE] Newsletter No.5, January 27, 2009
S B Cooper
pmt6sbc at maths.leeds.ac.uk
Tue Jan 27 16:37:12 EST 2009
CiE Newsletter No.5, January 27, 2009
___________________________________________________________________________
CONTENTS:
1. Logic Colloquium 2009, Sofia 31 July - 5 August
2. Workshop on Physics and Computation (PC'09)
3. THE SCIENCE AND PHILOSOPHY OF UNCONVENTIONAL COMPUTING (SPUC09)
4. COMPUTER SCIENCE LOGIC (CSL'09) - September 7-11, 2009, Coimbra, Portugal
5. Machines, Computations and Universality,
Carnegie Mellon University, Pittsburgh, September, 21-25, 2010
6. The Brian Michael Goldberg Memorial Award
7. Fall School of LOGIC & COMPLEXITY: NP Search
Problems and Algebraic Computation, Prague, 21-25 September 2009
8. 2009 GODEL Prize - CALL FOR NOMINATIONS
=========================================================================
1. (from Mariya Soskova)
*********************************************************************
First Announcement
Logic Colloquium 2009
Sofia 31 July - 5 August
Deadline for submissions: 15 April, 2009
http://lc2009.fmi.uni-sofia.bg
*********************************************************************
The Logic Colloquium is the annual European conference on logic,
organised under the auspices of the Association for Symbolic Logic
(ASL). The main events in this year's conference are as follows:
Gödel lecture:
* Richard A. Shore (Cornell University)
Tutorials:
* Ulrich Kohlenbach (Technische Universität Darmstadt)
* Andre Nies (University of Auckland)
* Ralf Schindler (Universität Münster)
Plenary talks:
* Elisabeth Bouscaren (Université Paris-Sud 11)
* S. Barry Cooper (University of Leeds),
* Thierry Coquand (University of Gothenburg),
* Ilijas Farah (York University)
* Valentina S. Harizanov (George Washington University)
* Stephan Kreutzer (Oxford University)
* David W. Kueker (University of Maryland)
* Benjamin Miller (University of California Los Angeles)
* Itay Neeman (University of California Los Angeles)
* Dana S. Scott (Carnegie Mellon University)
* Katrin Tent (University of Munster)
* Jouko Väänänen (University of Amsterdam)
Special sessions:
* Logic and Category Theory (Co-chairs: S. Abramsky, S. Shapiro)
* Computability Theory (Co-chairs: K. Ambos-Spies, I. Soskov)
* Model Theory, New Directions in Classification Theory (Co-chairs:
E. Hrushovski, M. Otero)
* Philosophical Logic (Co-chairs: D. Vakarelov, M. Zakharyashev)
* Set Theory (Co-chairs: M. Goldstern, H. Woodin)
Contributed papers will be selected from submissions received by the
PROGRAMME COMMITTEE consisting of:
Samson Abramsky, Klaus Ambos-Spies, Joan Bagaria (Chair), Fernando
Ferreira, Martin Goldstern, Erich Graedel, Ehud Hrushovski, Tapani
Hyttinen, Yiannis Moschovakis, Margarita Otero, Stewart Shapiro,
Ivan Soskov and W. Hugh Woodin
The Programme Committee cordially invites all researchers to submit
contributed papers that have logic research content that lies within the
scope of the interests of the ASL.
Submission Deadline: 15 April 2009
Notification of Authors: 31 April 2009
The abstracts of the contributed talks will be published in The Bulletin
of Symbolic Logic if at least one of the authors is a member of ASL. The
rules for abstract submission can be found at the conference webpage
http://lc2009.fmi.uni-sofia.bg.
The ASL will make available modest travel awards to graduate students in
logic and to recent PhDâ~@~Xs to attend the 2009 ASL European Summer Meeting
in Sofia, Bulgaria. The European Summer Meeting is also supported by a
grant from the US National Science Foundation; NSF funds may be awarded
only to students at USA universities and to citizens and permanent
residents of the USA.
Applications and recommendations must be received before the deadline of
March 30, 2009, by e-mail at lc2009 at fmi.uni-sofia.bg or by regular mail at:
LC2009
Alexandra Soskova
Dept. of Math Logic
Faculty of Mathematics and Informatics
Sofia University
boul. James Bourchier 5
1164, Sofia
Bulgaria
Phone: +359 02 8161 524
Fax: +359 02 8687180
by the Organizing Committee: Alexandra Soskova (Chair), Dimitar Dobrev,
Dimitar Guelev, Lyubomir Ivanov, Stela Nikolova, Solomon Passy, Dimitar
Shiyachki, Mariya Soskova, Mitko Yanchev, Anton Zinoviev
=========================================================================
2. (from Olivier Bournez) Workshop on Physics and Computation (PC'09)
**********************************************************************
CALL FOR PAPERS
Workshop on Physics and Computation
(PC'09)
http://www.lix.polytechnique.fr/~bournez/PC2009/pmwiki/pmwiki.php
September 7-11, 2009, Ponta-Delgada, Azores, Portugal
(Satellite event of UC'2009)
**********************************************************************
Physics and computation have interacted from the early days of
computing. Ultimately, physics laws permit computation. The aim of the
workshop is to bring together researchers with various interests in
the area to discuss important issues like fundamental physical limits
of computers, chaos and dynamical systems, quantum computers and
hypercomputation.
Topics of interest include (but are not limited to):
* Relativistic Computation
* Quantum Computing and Information
* Molecular Computing and Reaction Diffusion
* Dynamical Systems
* Randomness
* New models of computation
* Cellular automata
* Analog Computation
* Bio-inspired Computing
* Hypercomputation
**** Paper Submission Guidelines ****
Papers - maximum length 15 pages - must be submitted in PDF
to Olivier.Bournez at polytechnique.edu and Gilles.Dowek at polytechnique.edu
**** Important Dates ****
Deadline for submission: May 15th, 2009
Decision notification: July 7th, 2009
Workshop: September 7-11, 2009
Organizers:
Olivier Bournez (Ecole polytechnique)
Gilles Dowek (Ecole polytechnique and INRIA)
and the Organization team of UC'2009
Steering Committee:
Caslav Brukner (Vienna)
Christian Calude (Auckland)
Gregory Chaitin (IBM)
Jose-Felix Costa (Lisboa)
Istvan Nemeti (Budapest)
=========================================================================
3. (from Mark Hogarth) THE SCIENCE AND PHILOSOPHY
OF UNCONVENTIONAL COMPUTING (SPUC09) - second call for papers:
THE SCIENCE AND PHILOSOPHY OF UNCONVENTIONAL COMPUTING (SPUC09)
Cambridge (UK), March 23-25, 2009
SECOND CALL FOR PAPERS
We welcome submissions on topics normally classified under 'natural
computing' or 'unconventional computing' or 'hypercomputing'
including (but not restricted to) quantum computing, relativistic
computing, biology-based computing, analogue computing, and also
submissions on the philosophical implications of these new fields for
topics including (but again not restricted to) philosophy of mind,
philosophy of mathematics, the Church-Turing thesis.
Each presentation should last no more than 30 minutes; a further 10
minutes will be allowed for discussion.
Those wishing to make a presentation should submit by email a
250-word abstract of their paper to Mark Hogarth
(mhogarth at cantab.net); enquiries to the same.
Registration fee (yet to be fixed) will be around 100 ukp.
Student bursaries are available.
Conference
website: http://web.mac.com/mhogarth/Site/SPUC_Conference.html
ORGANISER
Mark Hogarth (Cambridge, UK)
CONFIRMED INVITED SPEAKERS
Selmer Brinsjord (New York, USA))
Jeff Barrett (Irvine, USA)
Philip Welch (Bristol, UK)
Tim Button (Harvard, USA)
Cristian Calude (Auckland, New Zealand))
Istvan Nemeti (Budapest, Hungry)
Benjamin Wells (San Francisco, USA)
Hajnal Andreka (Budapest, Hungry)
Apostolos Syropoulos (Xanthi, Greece)
Susan Stepney (York, UK)
Bruce MacLennan (Tennessee, USA)
Peter Kugel (Boston, USA)
Mark Sprevak (Cambridge, UK)
Selim Akl (Kingston, Canada)
Jose Felix Costa (Swansea, UK)
ADVISORY PANEL
Mike Stannett (Sheffield, UK)
John Tucker (Swansea, UK)
Barry Cooper (Leeds, UK)
Sponsored by EPSRC through HyperNet (the Hypercomputation Research
Network, EP/E064183/1)
______________________________
Dr M Hogarth
Leverhulme Research Fellow in Philosophy
Girton College
Cambridge CB3 0JG
T: 01223 338911
mhogarth at cantab.net
http://web.mac.com/mhogarth/
=========================================================================
4. (from Reinhard Kahle) COMPUTER SCIENCE LOGIC
(CSL'09) - September 7-11, 2009, Coimbra, Portugal:
********************************************************************
* CSL'09 *
* Annual Conference of the European Association for *
* Computer Science Logic *
* September 7 - 11, 2009, Coimbra, Portugal *
* http://www.mat.uc.pt/CSL09 *
* CALL FOR PAPERS *
********************************************************************
Computer Science Logic (CSL) is the annual conference of the European
Association for Computer Science Logic (EACSL). The conference is
intended for computer scientists whose research activities involve
logic, as well as for logicians working on issues significant for
computer science.
Suggested topics of interest include: automated deduction and
interactive theorem proving, constructive mathematics and type theory,
equational logic and term rewriting, automata and games, modal and
temporal logic, model checking, logical aspects of computational
complexity, finite model theory, computational proof theory, logic
programming and constraints, lambda calculus and combinatory logic,
categorical logic and topological semantics, domain theory, database
theory, specification, extraction and transformation of programs,
logical foundations of programming paradigms, verification and program
analysis, linear logic, higher-order logic, and nonmonotonic
reasoning.
Programme Committee: Invited Speakers:
Samson Abramsky (Oxford) Mikolaj Bojanczyk (Warsaw)
Matthias Baaz (Vienna) Thierry Coquand (Göteborg)
Patricia Bouyer (Cachan) Martin Grohe (Berlin)
Andrej Bulatov (Burnaby) Yiannis Moschovakis
Stephen Cook (Toronto) (Athens, Los Angeles)
Anuj Dawar (Cambridge) Paulo Oliva (London)
Hugo Gimbert (Bordeaux)
Erich Grädel (Aachen, co-chair)
Steffen Hölldobler (Dresden)
Gerhard Jäger (Berne)
Reinhard Kahle (Lisbon, co-chair)
AntonÃn KuÄ~Mera (Brno)
Benedikt Löwe (Amsterdam) Organizing Committee:
Simone Martini (Bologna)
Dale Miller (Paris) Ana Almeida (Coimbra, co-chair)
Luke Ong (Oxford) Sabine Broda (Porto)
Martin Otto (Darmstadt) José Carlos EspÃrito Santo (Braga)
Jean-Francois Raskin (Brussels) Mário Florido (Porto)
Thomas Schwentick (Dortmund) Gonçalo Gutierres (Coimbra)
Luc Segoufin (Cachan) Reinhard Kahle (Lisbon, co-chair)
AmÃlcar Sernadas (Lisbon) Isabel Oitavem (Lisbon)
Anton Setzer (Swansea) Pedro Quaresma (Coimbra, co-chair)
Helmut Veith (Darmstadt) João Rasga (Lisbon)
Thomas Wilke (Kiel) Carlota Simões (Coimbra)
Proceedings will be published in the LNCS series. Each paper accepted
by the Programme Committee must be presented at the conference by one
of the authors, and final copy prepared according to Springer's
guidelines.
Submitted papers must be in Springer's LNCS style and of no more than
15 pages, presenting work not previously published. They must not be
submitted concurrently to another conference with refereed
proceedings. The PC chair should be informed of closely related work
submitted to a conference or journal by 1 March 2009. Papers authored
or coauthored by members of the Programme Committee are not allowed.
Submitted papers must be in English and provide sufficient detail to
allow the Programme Committee to assess the merits of the paper. Full
proofs may appear in a technical appendix which will be read at the
reviewer's discretion. The title page must contain: title and
author(s), physical and e-mail addresses, identification of the
corresponding author, an abstract of no more than 200 words, and a
list of keywords.
The submission deadline is in two stages. Titles and abstracts must be
submitted by 30 March, 2009 and full papers by 6 April, 2009.
Notifications of acceptance will be sent by 25 May, 2009, and final
versions are due 22 June, 2009.
The Ackermann Award for 2009 will be presented to the recipients at
CSL'09.
********************************************************************
Important Dates:
Submission (title & abstract): 30 March, 2009
Submission (full paper) 6 April, 2009
Notification: 25 May, 2009
Final papers: 22 June, 2009
********************************************************************
Conference address:
CSL'09
c/o Prof. Pedro Quaresma
Departamento de Matemática
Universidade de Coimbra
Apartado 3008
P-3001-454 Coimbra
Portugal
http://www.mat.uc.pt/CSL09
csl at mat.uc.pt
=========================================================================
5. (from Maurice Margenstern) Machines,
Computations and Universality, Carnegie Mellon
University, Pittsburgh, September, 21-25, 2010:
MCU'2010
6th edition of the international conference
Machines, Computations and Universality,
place: Carnegie Mellon University, Pittsburgh
dates: September, 21-25, 2010
programme committee:
Erzsebet Csuhaj-Varju
Jérôme Durand-Lose (co-chair)
Vladik Kreinovich
Maurice Margenstern (co-chair)
Cris Moore
George Paun
Igor Potapov
Yurii Rogozhin
Klaus Sutner (co-chair)
Jiri Wiedermann
invited speakers:
Andrew Adamatzky
Olivbier Bournez
Mark Burgin
Jarkko Kari
Pascal Koiran
Kenichi Morita
Wilfried Sieg
Stephen Wolfram
Topics :
* Digital Computations (fundamental classical
models):
Turing machines, register machines, word
processing (groups and monoids), other
machines
* Digital models of computation:
cellular automata, other automata, tiling
of the plane, polyominoes, snakes, neural
networks, molecular computations
* Analog and Hybrid Computations:
BSS machines, infinite cellular automata,
real machines, quantum computing
In all these settings:
* frontiers between a decidable halting problem
and an undecidable one in the various
computational settings
* minimal universal codes:
size of such a code, namely, for Turing machines,
register machines, cellular automata, tilings,
neural nets, Post systems, ...
* computation complexity of machines with a
decidable halting problem as well as universal
machines
* connections between decidability under some
complexity class and completeness according to
this class
* self-reproduction and other tasks
* universality and decidability in the real field
A call for paper will be launched as soon as possible.
=========================================================================
6. (from Luciano Floridi) The Brian Michael Goldberg Memorial Award:
The Brian Michael Goldberg Memorial Award
The impact of research in Computational Modeling, Artificial
Intelligence, Machine Learning, Formal Models of Learning, and
Agent-based Simulations on the discipline of Philosophy has been
profound. Contemporary discussions of epistemology, ethics, theory of
mind, and philosophy of language have all benefited from lively,
interdisciplinary debates over the relation between computational and
formal models, and traditional philosophical questions. These debates
have found their way into scholarly publications and textbooks, as
well as into a growing number of Masters and Ph.D. theses.
In order to recognize outstanding achievements by Graduate Students
in this area of research and scholarship, the International
Association for Computing and Philosophy is proud to offer the "Brian
Michael Goldberg Memorial Award" for presentations in any category
listed above. This Award, which carries a $500 USD stipend, will be
presented each year at one of the North American Computing and
Philosophy conferences. Nominees and applicants are welcome from
around the world.
The department of philosophy at Carnegie Mellon is the sponsor of
this award and will serve as the site for submissions. The department
will establish an international committee to review applications and,
in conjunction with NA-CAP, will announce the yearly winner. Each
year's winner will be expected to make a presentation at a NA-CAP
conference as part of the Award Ceremony.
Submissions
Submissions are due on the same date as the regular submission
deadline for North American CAP Conferences (Feb 1st, 2009).
A complete submission consists of the following:
* Presentation (length should be appropriate for a one-hour
presentation)
* Presentation abstract, including your name and gradute program
(200 words)
* Email sent to mharrell at cmu.edu with the above two items as
attachements.
The Subject should be "Goldberg Award yourLastName".
The Body should consist of your full name, graduate program,
and a copy of the paper abstract.
Both documents should be in Microsoft Word or PDF format and composed
in English. Be advised that CAP discourages mere paper reading during
the presentation.
If you have any questions, please contact Mara Harrell
at mharrell at cmu.edu.
*********************************
Maralee Harrell
Associate Teaching Professor
Director of Student Teaching
Department of Philosophy
Carnegie Mellon University
135 Baker Hall
Pittsburgh, PA 15213
412-268-8152 tel
412-268-1440 fax mharrell at cmu.edu
=========================================================================
7. (from Iddo Tzameret) Fall School of LOGIC &
COMPLEXITY: NP Search Problems and Algebraic
Computation, Prague, 21-25 September 2009:
========================================================
Call for Participation
Fall School of LOGIC & COMPLEXITY:
NP Search Problems and Algebraic Computation
Prague, 21-25 September 2009
http://www.math.cas.cz/~krajicek/fall09.html
==========================================================
Guest Speakers:
* Samuel R. Buss (University of California, San Diego)
* Ran Raz (Weizmann Institute of Science, Rehovot)
Speakers from the Prague School will include:
* Pavel Pudlak
* Neil Thapen
Organization and contact: Jan Krajicek (krajicek at math.cas.cz)
PROGRAM:
The broad theme of the Fall Schools is the interaction of
Mathematical Logic and Complexity Theory, with a special emphasis on
Proof Complexity. A typical format of the school is this: we have two
series of lectures during Monday to Thursday, each usually two hours
per day. Some lectures (sometimes most of them) in the series are
delivered by guest speakers on a topic in logic or complexity theory
broadly relevant to the main theme of the school.
Starting this year we interpret the "School" as "Advanced School" but
the program should be available to dedicated students, willing to
learn a necessary material along the way (and perhaps study a
recommended literature in advance).
The special themes of this fall school will be:
1) NP Search Problems
Search problems are fundamental computational tasks. The problem is
determined by a binary relation R(x,y) with the property that for
each x there is a y such that R(x,y) holds. The task is to find some
solution y given an input x. The relation R is often polynomial time
decidable or in the class NP. There are many natural search problems
in all areas of discrete mathematics.
Search problems also naturally occur in Bounded Arithmetic as
characterizations of classes of functions definable in various
theories. The hierarchy of theories according to their strength
induces a hierarchy among search problems. This is closely linked
with the complexity of propositional logic. Reductions between search
problems are related to the existence of short proofs of one
combinatorial principle from another in a specific proof system.
Methods for showing non-reducibility draw directly from lower bound
methods in proof complexity. Many basic questions (e.g. the existence
of a complete NP search problem) are still open.
2) Algebraic Computation and Proofs
Algebraic (or arithmetic) circuits extend the realm of Boolean
complexity to a rich context of fields and rings. There is also
"algebraic" proof complexity: Algebraic proof systems (as are, for
example, the Nullstellensatz proof system or the Polynomial Calculus)
were studied in the last ten years or so and some interesting results
were obtained. In particular, these are rare proof systems for which
we can describe explicitly the class of formulas with short proofs.
In both of these areas there remain fundamental open problems.
This program is traditionally complemented by lectures of the
participants on their own work during Friday (there is no obligation
to deliver such a talk, though).
PARTICIPANTS: If you are interested to participate, please register
with Jan Krajicek (krajicek at math.cas.cz), and preferably before the
deadline April 15, 2009.
If you have not participated in an earlier Fall School, please
outline briefly your academic background. Everybody is, in principle,
welcome to participate. We are somewhat limited by available space
(maximum of 50 participants) so priority will be given to people
active in logic and/or complexity theory, and among those to doctoral
students and postdocs. I will try to accommodate also late applicants
but I cannot guarantee that there will be enough space.
For any additional information on the Fall School, please visit:
http://www.math.cas.cz/~krajicek/fall09.html
=========================================================================
8. (from Richard Ladner) 2009 GODEL Prize CALL FOR NOMINATIONS:
2009 GODEL Prize CALL FOR NOMINATIONS
The Goedel Prize for outstanding papers in the
area of theoretical computer science is sponsored
jointly by the European Association for
Theoretical Computer Science (EATCS) and the
Special Interest Group on Algorithms and
Computing Theory of the Association of Computing
Machinery (ACM-SIGACT). This award is presented
annually, with the presentation taking place
alternately at the International Colloquium on
Automata, Languages, and Programming (ICALP) and
ACM Symposium on the Theory of Computing (STOC).
The award will be given at STOC 2009 in
Washington D.C. The Prize is named in honor of
Kurt Goedel in recognition of his major
contributions to mathematical logic and of his
recently discovered interest in what has become
the famous "P versus NP" question. The Prize includes an award of $5000 (US).
AWARD COMMITTEE: The winner of the Prize is
selected by a committee of six members. The EATCS
President and the SIGACT Chair each appoint three members to the committee,
to serve staggered three-year terms. The committee is chaired alternately by
representatives of EATCS and SIGACT with the 2009 chair being a SIGACT
representative. The 2009 award committee consists of
Cynthia Dwork (Microsoft),
Shafi Goldwasser (Chair, MIT and Weizmann
Institute), Johan Håstad (KTH, Stockholm),
Jean-Pierre Jouannaud (LIX, Ecole Polytechnique),
Mike Paterson (University of Warwick), and Colin
Stirling (University of Edinburgh).
ELIGIBILITY: Any research paper or series of papers by a single author or
by a team of authors is deemed eligible if the paper was published in a
recognized refereed journal before nomination but the main results were not
published (in either preliminary or final form) in a journal or conference
proceedings before 1995 .This extended period is in recognition of the fact
that the value of fundamental work cannot always be immediately assessed.
The research nominated for the award should be in the area of theoretical
computer science. The term "theoretical computer science" is meant in a
broad sense, and encompasses, but is not restricted to, those areas covered
by ICALP and STOC. The Award Committee shall have the ultimate authority to
decide whether a particular paper is eligible for
the Prize. NOMINATIONS: Nominations for the
award should be submitted to the Award
Committee Chair at the following address:
Professor Shafi Goldwasser
Department of Computer Science and Applied Mathematics
The Weizmann Institute of Science Rehovot 76100,
Israel email: shafi at theory.csail.mit.edu
tel.: +972-8-934-2953 fax: +972-8-934-4122
To be considered, nominations for the 2009 prize must be received by January
31st, 2009. Nominations may be made by any member of the scientific
community. A nomination should contain a brief summary of the technical
content of the paper and a brief explanation of its significance. A copy of
the research paper or papers should accompany the nomination. The work may
be in any language. However, if it is not in English, a more extended
summary written in English should be enclosed. Additional recommendations in
favor of the nominated work may also be enclosed. To be considered for the
award, the paper or series of papers must be recommended by at least two
individuals, either in the form of two distinct nominations or one
nomination including recommendations from two
different people. It is the duty of the Award
Committee to actively solicit nominations from
as broad a spectrum of the theoretical computer science community as
possible, so as to ensure that potential award-winning papers are not
overlooked. To this end, the Award Committee will accept informal proposals
of potential nominees, as well as tentative offers to prepare formal
nominations, should they be needed to fulfill the requirements that the
paper have two separate recommendations.
SELECTION PROCESS: Although the Award Committee is encouraged to consult
with the theoretical computer science community at large, the Award
Committee is solely responsible for the selection of the winner of the
award. In the case that the Award Committee cannot agree on a recipient, the
prize may be shared by more than one paper or series of papers, and the
Award Committee reserves the right to declare no winner at all. All matters
relating to the selection process that are not specified here are left to
the discretion of the Award Committee.
=========================================================================
Items for the next CiE Newsletter should be sent to pmt6sbc at leeds.ac.uk
to arrive by February 6, 2009
-------------------------------------------------------------------------
More information about the FOM
mailing list