Programme of TAMC 2015
TAMC 2015 is held on
18, 19 and 20 May 2015
in the
Building
COM1 of the School of Computing of the National
University of Singapore in the Republic of Singapore. The talks are
in the room COM1#02-04 (SR2).
Including questions and answers, the invited talks have a duration of
60 minutes and the contributed talks have a duration of 25 minutes.
Sunday 17 May 2015 19:00 hrs: Reception in the Basement of Building
COM1 of the School of Computing, National University of Singapore
Monday 18 May 2015 08:50 hrs: Opening of the Conference
(in room COM1#02-04)
Monday 18 May 2015 09:00 hrs:
Talks 1 - 5: Recursion Theory, Logic and Complexity
(Chair: Frank Stephan)
1: Douglas Cenzer and Christopher Porter.
Algorithmically Random Functions and Effective Capacities.
2: Nadine Losert.
Where Join Preservation Fails in the Bounded Turing Degrees of C.E. Sets.
3: Kaspars Balodis, Janis Iraids and Rusins Freivalds.
Structured Frequency Algorithms.
4: Ning Ding.
Some New Consequences of the Hypothesis that P Has Fixed Polynomial-size
Circuits.
5: Maciej Bendkowski, Katarzyna Grygiel and Marek Zaionc.
Asymptotic properties of combinatory logic.
Monday 18 May 2015 11:05 hrs: Tea Break
Monday 18 May 2015 11:30 hrs: Invited Talk Alexandra Shlapentokh:
Easy
as ℚ: Hilbert's Tenth Problem for subrings of ℚ and
number fields. (Chair: Sanjay Jain)
Monday 18 May 2015 12:30 hrs: Lunchbreak
Monday 18 May 2015 14:00 hrs: Talks 6 - 9:
Boolean Functions and Combinatorics (Chair: Gopal T V)
6: Mitsunori Ogihara and Kei Uchizawa.
Computational Complexity Studies of Synchronous Boolean Finite Dynamical
Systems.
7: Raghav Kulkarni, Youming Qiao and Xiaoming Sun.
On the power of parity queries in Boolean decision trees.
8: Takuya Nishida, Yu-Ichi Hayashi, Takaaki Mizuki and Hideaki Sone.
Card-Based Protocols for Any Boolean Function.
9: Andris Ambainis and Jevgenijs Vihrovs.
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma.
Monday 18 May 2015 15:40 hrs: Teabreak
Monday 18 May 2015 16:05 hrs: Talks 10 - 14: Graph Theory 1
(Chair: Xiaoming Sun)
10: Xin He and Dayu He.
Star Shaped Orthogonal Drawing.
11: Anthony Bonato, Marc Lozier, Dieter Mitsche, Xavier Perez-Gimenez
and Pawel Pralat. The domination number of on-line social networks and
random geometric graphs.
12: Dayu He and Xin He.
A Linear Time Algorithm for Testing Almost Bipartite Graphs.
13: Nans Lefebvre.
The first-order contiguity of sparse random graphs with prescribed degrees.
14: Wanbin Son and Peyman Afshani.
Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls.
Tuesday 19 May 2015 09:00 hrs: Talks 15 - 19:
Quantum Computing, Parallelism and Statistics
(Chair: Alexandra Shlapentokh)
15: Zhaohui Wei and Shengyu Zhang.
Quantum game players can have advantage without discord.
16: Stefano Facchini and Simon Perdrix.
Quantum Circuits for the Unitary Permutation Problem.
17: Arash Farzan, Alejandro Lopez-Ortiz, Patrick K. Nicholson and
Alejandro Salinger. Algorithms in the Ultra-Wide Word Model.
18: Arijit Bishnu, Sameer Desai, Arijit Ghosh, Mayank Goswami and Subhabrata
Paul. Uniformity of point samples in metric spaces using gap ratio.
19: Ankush Das, Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi
and Dominik Wojtczak. On Pure Nash Equilibria in Stochastic Games.
Tuesday 19 May 2015 11:05 hrs: Teabreak
Tuesday 19 May 2015 11:30 hrs: Invited Talk Miklos Santha:
Quantum and randomized query complexity. (Chair: Shengyu Zhang)
Tuesday 19 May 2015 12:30 hrs: Lunchbreak
Tuesday 19 May 2015 14:00 hrs: Talks 20 - 23: Graph Theory 2
(Chair: Lance Fortnow)
20: Laurent Bulteau, Vincent Froese and Nimrod Talmon.
Multi-Player Diffusion Games on Graph Classes.
21: Takehiro Ito, Hirotaka Ono and Yota Otachi.
Reconfiguration of Cliques in a Graph.
22: Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa and Ryuhei Uehara.
Common Developments of Three Incongruent Boxes of Area 30.
23: Xujin Chen, Xiaodong Hu and Changjun Wang.
Finding Connected Dense k-Subgraphs.
Tuesday 19 May 2015 15:40 hrs: Teabreak
Tuesday 19 May 2015 16:05 hrs: Talks 24 - 26:
Learning, automata and probabilistic models
(Chair: Miklos Santha)
24: Lam Si Tung Ho, Vu Dinh, Nguyen Viet Cuong, Duy Duc Nguyen and
Binh T. Nguyen. Learning From Non-iid Data: Fast Rates for the One-vs-All
Multiclass Plug-in Classifier.
25: Joey Eremondi, Oscar Ibarra and Ian McQuillan.
Deletion Operations on Deterministic Families of Automata.
26: Reema Patel, Kevin Patel and Dhiren Patel.
ExplicitPRISMSymm: Symmetry Reduction Technique for Explicit Models in PRISM.
Tuesday 19 May 2015 17:30 hrs: Bus to Dinner at
Night Safari
(dinner in a restaurant there with subsequent visit of the night zoo;
return bus at 22:00 hrs to Buona Vista MRT)
Wednesday 20 May 2015 09:00 hrs: Talks 27 - 31:
Graph Theory 3 (Chair: Yota Otachi)
27: Laurent Bulteau, Stefan Fafianie, Vincent Froese, Rolf Niedermeier
and Nimrod Talmon. The Complexity of Finding Effectors.
28: Sepp Hartung and Nimrod Talmon.
The Complexity of Degree Anonymization by Graph Contractions.
29: Mingyu Xiao and Huan Tan.
An Improved Exact Algorithm for Maximum Induced Matching.
30: Alexandre Talon and Jan Kratochvil.
Completion of the mixed-unit interval graphs hierarchy.
31: Nikhil Balaji and Samir Datta.
Bounded Treewidth and Space-Efficient Linear Algebra.
Wednesday 20 May 2015 11:05 hrs: Teabreak
Wednesday 20 May 2015 11:30 hrs: Invited Talk
Lance Fortnow:
Nondeterministic Separations.
(Chair: Rodney G. Downey)
Wednesday 20 May 2015 12:30 hrs: Lunchbreak
Wednesday 20 May 2015 14:00 hrs: Talks 32 - 35:
Parameterised Complexity (Chair: Barry Cooper)
32: Henning Fernau, Alejandro Lopez-Ortiz and Jazmín Romero.
Kernelization Algorithms for Packing Problems Allowing Overlaps.
33: Robert Ganian, Martin Kronegger, Andreas Pfandler and Alexandru Popa.
Parameterized Complexity of Asynchronous Border Minimization.
34: Pavel Dvořák and Dusan Knop.
Parametrized complexity of length-bounded cuts and multi-cuts.
35: Jin-Yong Lin and Sheung-Hung Poon.
Hardness and Algorithms on Signed Domination.
Wednesday 20 May 2015 15:40 hrs: Teabreak
Wednesday 20 May 2015 16:05 hrs: Special Session Talks
(Chair: Guohua Wu)
a: Rodney G. Downey. Courcelle's Theorem for Triangulations.
b: Gopal T V. Beautiful Code - Circularity and Anti-Foundation Axiom.
c: Barry Cooper. Why Do We Compute? The Meaning of Computation.
Adjorn
Abstracts of Special Session Talks
Rodney G. Downey.
Courcelle's Theorem for Triangulations.
Courcelle's Theorem is a famous theorem in graph theory which says that
for graphs of bounded treewidth, MSO properties are linear time
recognizable. With Benjamin Burton, we prove a similar result in low
dimensional topology.
Gopal T V. Beautiful Code - Circularity and Anti-Foundation Axiom.
Computing is essentially a combination of theoretical, scientific, and
engineering traditions. Programming is a process of mapping the computing
problem into a form that can be executed on an automaton. Modeling the
application in terms of well-defined structures and algorithms is the
most important step towards evolving a solution. This talk demonstrates
Literate Programming and Software Aesthetics as two best
practices that may result in deciding early the beautiful solutions that
can be verified and validated.
Barry Cooper. Why Do We Compute? The Meaning of Computation.
The stepping-off point for this brief talk is Samson Abramsky's innocent
question from his contribution "Two Puzzles About Computation" to "Alan
Turing: his work and impact" (S.B. Cooper and J. van Leeuwen, eds., pages
53-57, Elsevier 2013).
Computation is both an activity and a semantical conduit. And how
computation (or more specifically arithmetic) is described blurs the
boundaries between the two. In this talk we discuss the relationship
between computation and semantics, and the mathematical and linguistic
interconnections at work. Abramsky's question connects both with the
seminal thinking of Alan Turing on higher order computation and the role
of typing of information; and with deep questions in today's computer
science concerning the scope and social context of computational
embodiment and universality.