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.

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.