TAMC 2015 aims at bringing
together a wide range of researchers with interests in computational
theory and applications. For more than 10 years, the conference
series Theory and Applications of Models of Computing has fostered
interactions and collaborations between both theoretical and applied
researchers working on all aspects of computations and the ways to model it.
Accepted Papers: There are 35 accepted
papers out of 78 submissions; the acceptance rate is 44.87%.
Registration: The registration was open at
and the fees have been SGD 750 (full paying, early rate),
SGD 880 (full paying, late rate), SGD 600 (undergraduate
or postgraduate student, early rate), SGD 730 (student, late rate).
The early rate applies prior to the corresponding deadline 2 April 2015.
The venue of TAMC 2015 is the building COM1 of
the School of Computing
and the reception as well as the talks will be held in this building.
The talks will be in the room COM1#02-04 (SR2).
Several hotels commited to give a promotional rate for
participants of the conference, see the attached pdf-files for more
information. When booking one of these hotels, please indicate
that you are participating TAMC 2015 organised by NUS in the case
that the hotel asks for this. The prices include include internet
and breakfast unless noted otherwise.
These hotels are the following ones:
Pasir Panjang Inn **
(SGD 118 per night without breakfast, SGD 125 per night with breakfast)
in walking distance from the conference venue;
Grand Copthorne Waterfront
Hotel ***** (SGD 245++ per night, see form) situated near the
Singapore River in the Clarke Quay area
of Singapore; this hotel provides two-way transport complimentary provided
that enough people of the conference book into it; taxis might cost about
SGD 20 each way to and from the conference location;
Orchard Hotel Singapore ***** (SGD
250++ per night, see form) which
is situated in the Orchard Road, Singapore's traditional premium shopping road;
this hotel provides two-way transport complimentary provided that enough people
of the conference book into it; taxis might cost about SGD 20 each way to
and from the conference location.
Transport in Singapore:
The MRT stations nearest to the conference location are Haw Par
Villa MRT and Kent Ridge MRT. From Haw Par Villa or also from Habourfront
MRT, one can go by bus 10 or 30 or 143 to bus stop "Pasir Panjang Road,
Heng Mui Keng Terrace" and from their walk about 10 to 15 minutes
to the School of Computing. From Kent Ridge MRT one can walk (about
25 minutes) or take a cost-free internal shuttle bus (about 30 minutes) to
the School of Computing.
One can also flag on the street a taxi or book one through the telephone
numbers provided by the
Land Transport Authority of Singapore. A taxi from
downtown Singapore to the
conference location costs about SGD 20.
A taxi from the airport to the hotel costs depending on day time
and traffic condition between SGD 25 and SGD 45.
(Georgia Institute of Technology):
We survey recent research on the power of nondeterministic computation and
how to use nondeterminism to get new separations of complexity classes.
Results include separating NEXP from NP with limited advice, a new proof of
the nondeterministic time hierarchy and a surprising relativized world
where NP is as powerful as NEXP infinitely often.
Santha (CNRS, Université Paris Diderot and CQT,
National University of Singapore):
Quantum and randomized query complexity.
We survey recent classical characterizations of quantum query
complexity and new methods to obtain quantum query algorithms.
Particular emphasis will be given to learning graphs, a combinatorial
way to conceive quantum query algorithms. We will briefly sketch
attempts to find analogous characterizations of randomized query
complexity, and the difficulties encountered.
(East Carolina University): Easy as ℚ: Hilbert's Tenth Problem
for subrings of ℚ and number fields.
Hilbert's Tenth Problem was a question posed by Hilbert
concerning algorithmic solvability of polynomial equations with integer
coefficients over ℤ. Davis, Putnam, Robinson and Matiyasevich proved
that such an algorithm does not exist. The last part of this proof was
completed in 1970. The analogous question for ℚ is still open. We
briefly review the history of attempts to resolve the Diophantine status
of ℚ and discuss some recent approaches to this question by
considering subrings of ℚ where Hilbert's Tenth Problem is Turing
equivalent to Hilbert's Tenth Problem over ℚ.
TAMC 2015 is open for all topics relating to the theory
and applications of models of computation. The topics include algebraic
computation, algorithmic coding and number theory, algorithmic
learning theory, approximation algorithms,
automata theory, circuit complexity, communication complexity, complex
networks and their theory,
combinatorial algorithms, computability
and recursion theory, computational biology, computational complexity,
computational geometry, continuous and real computation, cryptography,
data structures, design and analysis of algorithms, distributed algorithms,
domain models, fixed parameter tractability, formal languages, game theory,
geometric algorithms, grammatical inference, graph algorithms,
graph mining, information theory, internet mathematics,
memory hierarchy tradeoffs, model theory for computing, natural computing,
network algorithms, network security and applications, online algorithms,
optimisation, parallel algorithms,
philosophy of computing, privacy and security, property testing,
proof complexity, process models, quantum computation, randomness,
randomised algorithms, space-time tradeoffs, streaming algorithms,
systems theory, VLSI models of computation.