Theory and applications of models of computation. 12th annual conference, TAMC 2015, Singapore, May 18–20, 2015. Proceedings. (English) Zbl 1320.68020

Lecture Notes in Computer Science 9076. Cham: Springer (ISBN 978-3-319-17141-8/pbk; 978-3-319-17142-5/ebook). xii, 466 p. (2015).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1284.68014].
Indexed articles:
Shlapentokh, Alexandra, Hilbert’s tenth problem for subrings of \(\mathbb Q\) and number fields (extended abstract), 3-9 [Zbl 1459.11233]
Fortnow, Lance, Nondeterministic separations, 10-17 [Zbl 1459.68075]
Cenzer, Douglas; Porter, Christopher P., Algorithmically random functions and effective capacities, 23-37 [Zbl 1461.03037]
Losert, Nadine, Where join preservation fails in the bounded Turing degrees of c.e. sets, 38-49 [Zbl 1391.03029]
Balodis, Kaspars; Iraids, Jānis; Freivalds, Rūsiņš, Structured frequency algorithms, 50-61 [Zbl 1461.03032]
Bendkowski, Maciej; Grygiel, Katarzyna; Zaionc, Marek, Asymptotic properties of combinatory logic, 62-72 [Zbl 1461.03015]
Ding, Ning, Some new consequences of the hypothesis that P has fixed polynomial-size circuits, 75-86 [Zbl 1460.68041]
Ogihara, Mitsunori; Uchizawa, Kei, Computational complexity studies of synchronous Boolean finite dynamical systems, 87-98 [Zbl 1459.68084]
Kulkarni, Raghav; Qiao, Youming; Sun, Xiaoming, On the power of parity queries in Boolean decision trees, 99-109 [Zbl 1460.68033]
Nishida, Takuya; Hayashi, Yu-ichi; Mizuki, Takaaki; Sone, Hideaki, Card-based protocols for any Boolean function, 110-121 [Zbl 1353.94067]
Ambainis, Andris; Vihrovs, Jevgēnijs, Size of sets with small sensitivity: a generalization of Simon’s lemma, 122-133 [Zbl 1352.05180]
He, Xin; He, Dayu, Star shaped orthogonal drawing, 137-149 [Zbl 1352.05131]
Bonato, Anthony; Lozier, Marc; Mitsche, Dieter; Pérez-Giménez, Xavier; Prałat, Paweł, The domination number of on-line social networks and random geometric graphs, 150-163 [Zbl 1462.05271]
He, Dayu; He, Xin, A linear time algorithm for determining almost bipartite graphs, 164-176 [Zbl 1460.68075]
Lefebvre, Nans, The first-order contiguity of sparse random graphs with prescribed degrees, 177-188 [Zbl 1461.03026]
Son, Wanbin; Afshani, Peyman, Streaming algorithms for smallest intersecting ball of disjoint balls, 189-199 [Zbl 1459.68234]
Bulteau, Laurent; Froese, Vincent; Talmon, Nimrod, Multi-player diffusion games on graph classes, 200-211 [Zbl 1462.05252]
Ito, Takehiro; Ono, Hirotaka; Otachi, Yota, Reconfiguration of cliques in a graph, 212-223 [Zbl 1462.05280]
Bulteau, Laurent; Fafianie, Stefan; Froese, Vincent; Niedermeier, Rolf; Talmon, Nimrod, The complexity of finding effectors, 224-235 [Zbl 1362.68101]
Xu, Dawei; Horiyama, Takashi; Shirakawa, Toshihiro; Uehara, Ryuhei, Common developments of three incongruent boxes of area 30, 236-247 [Zbl 1459.52014]
Chen, Xujin; Hu, Xiaodong; Wang, Changjun, Finding connected dense \(k\)-subgraphs, 248-259 [Zbl 1459.68155]
Hartung, Sepp; Talmon, Nimrod, The complexity of degree anonymization by graph contractions, 260-271 [Zbl 1459.68158]
Xiao, Mingyu; Tan, Huan, An improved exact algorithm for maximum induced matching, 272-283 [Zbl 1459.05318]
Talon, Alexandre; Kratochvil, Jan, Completion of the mixed unit interval graphs hierarchy, 284-296 [Zbl 1459.05218]
Balaji, Nikhil; Datta, Samir, Bounded treewidth and space-efficient linear algebra, 297-308 [Zbl 1460.68043]
Wei, Zhaohui; Zhang, Shengyu, Quantum game players can have advantage without discord, 311-323 [Zbl 1461.91075]
Facchini, Stefano; Perdrix, Simon, Quantum circuits for the unitary permutation problem, 324-331 [Zbl 1459.81030]
Farzan, Arash; López-Ortiz, Alejandro; Nicholson, Patrick K.; Salinger, Alejandro, Algorithms in the ultra-wide word model, 335-346 [Zbl 1460.68014]
Bishnu, Arijit; Desai, Sameer; Ghosh, Arijit; Goswami, Mayank; Paul, Subhabrata, Uniformity of point samples in metric spaces using gap ratio, 347-358 [Zbl 1460.68078]
Das, Ankush; Krishna, Shankara Narayanan; Manasa, Lakshmi; Trivedi, Ashutosh; Wojtczak, Dominik, On pure Nash equilibria in stochastic games, 359-371 [Zbl 1461.91029]
Dinh, Vu; Ho, Lam Si Tung; Cuong, Nguyen Viet; Nguyen, Duy; Nguyen, Binh T., Learning from non-iid data: fast rates for the one-vs-all multiclass plug-in classifiers, 375-387 [Zbl 1459.68169]
Eremondi, Joey; Ibarra, Oscar H.; McQuillan, Ian, Deletion operations on deterministic families of automata, 388-399 [Zbl 1459.68100]
Patel, Reema; Patel, Kevin; Patel, Dhiren, ExplicitPRISMSymm: symmetry reduction technique for explicit models in PRISM, 400-412 [Zbl 1459.68122]
Fernau, Henning; López-Ortiz, Alejandro; Romero, Jazmín, Kernelization algorithms for packing problems allowing overlaps, 415-427 [Zbl 1460.68074]
Ganian, Robert; Kronegger, Martin; Pfandler, Andreas; Popa, Alexandru, Parameterized complexity of asynchronous border minimization, 428-440 [Zbl 1459.68085]
Dvořák, Pavel; Knop, Dušan, Parametrized complexity of length-bounded cuts and multi-cuts, 441-452 [Zbl 1454.68056]
Lin, Jin-Yong; Poon, Sheung-Hung, Algorithms and hardness for signed domination, 453-464 [Zbl 1459.68161]


68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
00B25 Proceedings of conferences of miscellaneous specific interest


Zbl 1284.68014
Full Text: DOI