Theory and Applications of Models of Computation (TAMC 2012)

Turing Lectures
• John E. Hopcroft: On the Impact of Turing Machines.

• S. Barry Cooper: From Turing Machine to Morphogenesis: Forming and Informing Computation.

• Richard M. Karp: Theory of Computation as an Enabling Tool for the Sciences.

• Deyi Li, Liwei Huang: Interaction and Collective Intelligence on the Internet.

• Butler W. Lampson: What Computers Do: Model, Connect, Engage.

• Wei Li: R-Calculus: A Logical Inference System for Scientific Discovery.

• Andrew Chi-Chih Yao: Quantum Computing: A Great Science in the Making.

• Jon M. Kleinberg: The Convergence of Social and Technological Networks.

Invited Lectures
• Yicheng Pan: Principles of Network Computing.

• Pan Peng: The Small Community Phenomenon in Networks: Models, Algorithms and Applications.

• Anthony Bonato, Dieter Mitsche, Pawel Pralat: Vertex-Pursuit in Hierarchical Social Networks.

• Zipeng Zhang, Xinyu Feng, Ming Fu, Zhong Shao, Yong Li: A Structural Approach to Prophecy Variables.

• Shuling Wang, Naijun Zhan, Dimitar P. Guelev: An Assume/Guarantee Based Compositional Calculus for Hybrid CSP.

• Ernst-Rüdiger Olderog: Automatic Verification of Real-Time Systems with Rich Data: An Overview.

• Deepak Kapur: Program Analysis Using Quantifier-Elimination Heuristics.

• Albert F. Lawrence, Sebastien Phan, Mark H. Ellisman: Electron Tomography and Multiscale Biology.

Contributed Papers
• Hiro Ito, Susumu Kiyoshima, Yuichi Yoshida: Constant-Time Approximation Algorithms for the Knapsack Problem.

• Jingguo Bi, Qi Cheng: Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices.

• Michal Cerný, Miroslav Rada: Polynomial Time Construction of Ellipsoidal Approximations of Zonotopes Given by Generator Descriptions.

• Alexandru Popa, Prudence W. H. Wong, Fencol C. C. Yung: Hardness and Approximation of the Asynchronous Border Minimization Problem - (Extended Abstract).

• Kun-Mao Chao, An-Chiang Chu, Jesper Jansson, Richard S. Lemence, Alban Mancheron: Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics.

• Samir Datta, Rameshwar Pratap: Computing Bits of Algebraic Numbers.

• Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire: Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms.

• Guizhen Zhu, Daqing Wan: Computing Error Distance of Reed-Solomon Codes.

• Deshi Ye, Guochuan Zhang: Coordination Mechanisms for Selfish Parallel Jobs Scheduling - (Extended Abstract).

• Andrew C. Yao, Yunlei Zhao: Computationally-Fair Group and Identity-Based Key-Exchange.

• Shaoquan Jiang: Timed Encryption with Application to Deniable Key Exchange.

• Sheng Yu, Jude-Thaddeus Ojiaku, Prudence W. H. Wong, Yinfeng Xu: Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines.

• Jun Yan: A Surprisingly Simple Way of Reversing Trace Distance via Entanglement.

• Jun Zhang, Fang-Wei Fu: Constructions for Binary Codes Correcting Asymmetric Errors from Function Fields.

• Jun Zhang, Fang-Wei Fu, Daqing Wan: Stopping Set Distributions of Algebraic Geometry Codes from Elliptic Curves.

• Lin Wang, Antonio Fernández Anta, Fa Zhang, Chenying Hou, Zhiyong Liu: Energy-Efficient Network Routing with Discrete Cost Functions.

• Xiao Yang, Florian Sikora, Guillaume Blin, Sylvie Hamel, Romeo Rizzi, Srinivas Aluru: An Algorithmic View on Multi-Related-Segments: A Unifying Model for Approximate Common Interval.

• Hervé Baumann, Pierre Fraigniaud, Hovhannes A. Harutyunyan, R. de Verclos: The Worst Case Behavior of Randomized Gossip.

• Zhiguo Fu, Jin-Yi Cai: Holographic Algorithms on Domain Size k > 2.

• Mingyu Xiao, Hiroshi Nagamochi: A Refined Exact Algorithm for Edge Dominating Set.

• Aniruddh Gandhi, Bakhadyr Khoussainov, Jiamou Liu: Finite Automata over Structures - (Extended Abstract).

• Nathaniel Hobbs, Yuexuan Wang, Qiang-Sheng Hua, Dongxiao Yu, Francis C. M. Lau: Deterministic Distributed Data Aggregation under the SINR Model.

• Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima: Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication.

• Weiwei Wu, Minming Li, He Huang, Enhong Chen: Speed Scaling Problems with Memory/Cache Consideration.

• Sanjay Jain, Frank Stephan, Thomas Zeugmann: On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data.

• Denys Duchier, Jérôme Durand-Lose, Maxime Senot: Computing in the Fractal Cloud: Modular Generic Solvers for SAT and Q-SAT Variants.

• Mordechai Shalom, Ariella Voloshin, Prudence W. H. Wong, Fencol C. C. Yung, Shmuel Zaks: Online Optimization of Busy Time on Parallel Machines.

• Jordi Arjona Aroca, Antonio Fernández Anta: Bisection (Band)Width of Product Networks with Application to Data Centers.

• Beate Bollig, Marc Gillé, Tobias Pröger: Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations.

• Jin Li, Weiyi Liu, Kun Yue: A Game-Theoretic Approach for Balancing the Tradeoffs between Data Availability and Query Delay in Multi-hop Cellular Networks.

• Teng Long, Wenhui Zhang: Proving Liveness Property under Strengthened Compassion Requirements.

• Eugen Jiresch, Bernhard Gramlich: Realizing Monads in Interaction Nets via Generic Typed Rules.

• Olivier Bournez, Nachum Dershowitz, Evgenia Falkovich: Towards an Axiomatization of Simple Analog Algorithms.

• Rusins Freivalds: Multiple Usage of Random Bits in Finite Automata.

• Taisuke Izumi, Tomoko Izumi, Hirotaka Ono, Koichi Wada: Minimum Certificate Dispersal with Tree Structures.

• Jianxin Wang, Jinyi Yao, Qilong Feng, Jianer Chen: Improved FPT Algorithms for Rectilinear k-Links Spanning Path.

• Ying Zheng, Jianxin Wang, Qilong Feng, Jianer Chen: FPT Results for Signed Domination.

• Hiroshi Nagamochi: Submodular Minimization via Pathwidth.

• Martin Nehéz, Daniel Olejár, Michal Demetrian: A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs.

• Liliana Badillo, Charles M. Harris: An Application of 1-Genericity in the $\Pi^0_2$ Enumeration Degrees.