| TAMC07 Program Schedule (PDF Download) | ||||||
| http://www.tamc2007.fudan.edu.cn | ||||||
| Lecture Hall= Room A: Multi-Purpose Room(2nd Floor, Grand Hotel) Room B: the 3rd Meeting Room(1st Floor, Grand Hotel) | ||||||
| May 22nd | ||||||
| Plenary talk(Chair: Jin Yi Cai) | Lecture Hall | |||||
| 9:00-10:00 | Fan Chung Graham (UCSD) | Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm | ||||
| Short Break (Photo Taking) | ||||||
| Session 1 (Chair: Hong Zhu) | Room A | Session 2(Chair: Decheng Ding) | Room B | |||
| 10:30-10:55 | Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thoele and Henning Thomas | Approximation Algorithms for 3D Orthogonal Knapsack | 10:30-10:55 | Angsheng Li | Elementary Differences Among Jump Hierarchies | |
| 10:55-11:20 | Qi Cheng and Elizabeth Murray | On Deciding Deep Holes of Reed-Solomon Codes | 10:55-11:20 | George Barmpalias, Andrew Lewis and Mariya Ivanova Soskova | Working with the LR Degrees | |
| 11:20-11:45 | Haiyang Hou and Guochuan Zhang | The Hardness of Selective Network Design for Bottleneck Routing Games | 11:20-11:45 | Yatao Xu and Tanja Grubba | Computability on Subsets of Locally Compact Spaces | |
| 11:45-12:10 | Hitoshi Yamasaki and Takayoshi Shoudai | A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns | 11:45-12:10 | Shin-ishi Nakano, Ryuhei Uehara and Takeaki Uno | A New Approach to Graph Recognition and Applications to Distance Hereditary Graphs | |
| Lunch | ||||||
| Special Session on Algorithms and Complexity (Room A) (Chair: Manidra Agrawal) | ||||||
| 13:30-14:15 | Jin-Yi Cai | Holographic Algorithms | ||||
| 14:15-15:00 | Naveen Garg | Fractional Packing and Covering | ||||
| Short Break (Chair: Ansheng Li) | ||||||
| 15:15-16:00 | Jaikumar Radhakrishnan | The PCP Theorem's New Proof | ||||
| 16:00-16:45 | Manindra Agrawal | Determinant versus Permanent | ||||
| Short Break (Chair: Ansheng Li) | Regular Session (Room B)(Chair: Osamu Watanabe) | |||||
| 17:00-17:45 | Alberto Apostolico | Faster Algorithms for the Extraction of Irredundant Motif Bases | 17:00-17:25 | Jun Tarui | Finding a Duplicate and a Missing Item in a Stream | |
| 17:25-17:50 | Peng Zhang. | An Approximation Algorithm to the k-Steiner Forest Problem | ||||
| 17:50-18:15 | Jin Wang, Daxing Li and Xi Bai | Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem | ||||
| May 23rd | ||||||
| Plenary talk(Chair: S.B.Cooper) | Lecture Hall | |||||
| 9:00-10:00 | Miklos Ajtai (IBM Research) | Generalizations of the Compactness Theorem and Godel's Completeness Theorem for Nonstandard Finite Structures | ||||
| Short Break | ||||||
| Session 1(Chair: Janos Simon) | Room A | Session 2(Chair: Andre Nies) | Room B | |||
| 10:20-10:45 | Rongquan Feng and Hongfeng Wu | Encapsulated scalar multiplications and line functions in the computation of Tate pairings | 10:20-10:45 | Mariya Ivanova Soskova and S. Barry Cooper | The Strongest Nonsplitting Theorem | |
| 10:45-11:10 | Xiaoming Hu and Shanghuang Teng | A Provably Secure Blind Signature Scheme | 10:45-11:10 | Fan Yun | There is an sw-cuppable strongly c.e. real | |
| 11:10-11:35 | Pei shi hui, Zhao yong zhe and Zhao hong wei | Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2) | 11:10-11:35 | Pan Li, Zhao Weidong, Wang Zhicheng and Wei Gang | The Concurrently Enabled Transition Set Problem for Petri Nets is NP-complete | |
| 11:35-12:00 | Fanyu Kong, Jia Yu, Zhun Cai and Daxing Li | New Left-to-right Radix-r Signed-digit Recoding Algorithm for Pairing-based Cryptosystems | 11:35-12:00 | Trahtman A.N. | Synchronization of some DFA | |
| Lunch | ||||||
| Session 1(Chair: C.K.Poon) | Room A | Session 2(Chair: Qi Cheng) | Room B | |||
| 13:30-13:55 | Sheng-Lung Peng and Yi-Chuan Yang | On the treewidth and pathwidth of biconvex bipartite graphs | 13:30-13:55 | Minming Li, Ze Feng, Ronald L. Graham and Frances Yao | Approximately Optimal Trees for Group Key Management with Batch Updates | |
| 13:55-14:20 | Andrzej Lingas and Martin Wahlen | On Exact Complexity of Subgraph Homeomorphism | 13:55-14:20 | S. Q. Zheng, Bing Yang and Enyue Lu | Comparative Study of Efficient Algorithms for Partitioning Sequences into Subsequences | |
| 14:20-14:45 | Xuehou Tan | Searching a polygonal region by two guards | 14:20-14:45 | Iordanis Kerenidis | Quantum multiparty communication complexity and circuit lower bounds | |
| 14:45-15:10 | Sun-Yuan Hsieh, Huang-Ming Gao and Shih-Cheng Yang | On the Internal Steiner Tree Problem | 14:45-15:10 | Feng Liu and Keqin Feng | Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions | |
| Short Break | ||||||
| Session 1(Chair: C.S.Calude) | Room A | Session 2(Chair: Hong Zhu) | Room B | |||
| 15:25-15:50 | Andreas Jakoby, Maciej Liskiewicz, Ruediger Reischuk and Christian Schindelhauer. | Improving the Average Delay of Sorting | 15:25-15:50 | Jin Yi and Wenhui Zhang. | Enhancing Simulation for Checking Language Containment | |
| 15:50-16:15 | Ehab Morsy and Hiroshi Nagamochi. | Approximating Capacitated Tree-Routings in Networks | 15:50-16:15 | Conghua Zhou, Zhenyu Chen and Zhihong Tao. | QBF-based Symbolic Model Checking for Knowledge and Time | |
| 16:15-16:40 | Sushmita Gupta. | Feedback Arc Set Problem in Bipartite Tournaments | 16:15-16:40 | Cristina Tirnauca and Satoshi Kobayashi. | A Characterization of the Language Classes Learnable with Correction Queries | |
| 16:40-17:05 | Yufeng Wang, Yoshiaki Hori and Kouichi Sakurai. | Studying on economic-inspired mechanism for routing and forwarding in wireless Ad hoc network | 16:40-17:05 | Zhimin Li and Xiang Li. | Learnable Algorithm on the Continuum | |
| Short Break | ||||||
| Session 1(Chair: Manindra Agrawal) | Room A | Session 2(Chair: Rudolf Fleischer) | Room B | |||
| 17:20-17:45 | Joseph Wun-Tat Chan, Tak-Wah Lam, Kin-Sum Mak and Prudence W.H. Wong. | Online Deadline Scheduling with Bounded Energy Efficiency | 17:20-17:45 | YONG LI and Jun-Hai Yong. | Efficient exact arithmetic over constructive reals | |
| 17:45-18:30 | Andreas Dress, Vincent Moulton, Kathi Huber and Jack Koolen. | Virtual cut points of metric spaces -- what are they good for, and how can one compute them? | 17:45-18:10 | MV Panduranga Rao. | Bounding run-times of local adiabatic algorithms | |
| 18:10-18:35 | Shin-ishi Nakano, Ryuhei Uehara and Takeaki Uno. | Efficient Algorithms for Airline Problem | ||||
| May 24th | ||||||
| Special Session on Computability and Randomness (Lecture Hall)(Chair: S.B.Cooper) | ||||||
| 8:45-9:30 | Jan Reimann. | Effectively closed sets of measures and randomness | ||||
| 9:30-10:15 | Bjorn Kjos-Hansen. | Brownian Motion and Kolmogorov Complexity | ||||
| 10:15-11:00 | C. S. Calude (University of Auckland, NZ) | Most Programs Stop Quickly or Never Halt (joint work with M. A. Stay, University of California Riverside, USA) | ||||
| Short Break | ||||||
| TOUR | ||||||
| May 25th | ||||||
| Session 1(Chair: Jianer Chen) | Room A | Session 2(Chair: Hanpin Wang) | Room B | |||
| 8:45- 9:10 | Andrew C. C. Yao, Frances F. Yao and Yunlei Zhao. | A Note on Universal Composable Zero-Knowledge in the Common Reference String Model | 8:45- 9:10 | Chuzo Iwamoto, Harumasa Yoneda, Kenichi Morita and Katsunobu Imai. | A Time Hierarchy Theorem for Nondeterministic Cellular Automata | |
| 9:10- 9:35 | Andrew C. C. Yao, Frances Yao and Yunlei Zhao. | A Note on the Feasibility of Generalized Universal Composability | 9:10- 9:35 | zhenhua duan and cong tian. | Decidability of Propositional Projection Temporal Logic with Infinite Models | |
| 9:35-10:00 | Markus Hinkelmann, Andreas Jakoby and Peer Stechert. | t-Private and Secure Auctions | 9:35-10:00 | Hong Ryoo and Kwangsoo Kim. | Separation of Data via Concurrently Determined Discriminant Functions | |
| 10:00-10:25 | Takaaki Mizuki, Yoshinori Kugimoto and Hideaki Sone. | Secure Multiparty Computations Using a Dial Lock | 10:00-10:25 | Stuart Kurtz and Janos Simon. | The Undecidability of the Generalized Collatz Problem | |
| Short Break | ||||||
| Special Session on Computability and Randomness (Lecture Hall)(Chair: Hong Zhu) | ||||||
| 10:30-11:15 | George Barmpalias (Leeds) | Lowness, Randomness and Degrees | ||||
| 11:15-12:00 | Andre Nies (Auckland) | Randomness, computability, and effective descriptive set theory | ||||
| Lunch | ||||||
| Session 1(Chair:Ruediger Reischuk) | Room A | Session 2(Chair: Rudolf Fleischer) | Room B | |||
| 13:30-13:55 | Yingchao Zhao and Shanghua Teng. | Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces | 13:30-13:55 | Decheng Ding, Klaus Weihrauch and Yongcheng wu. | Absolutely Non-Effective Predicates and Functions in Computable Analysis | |
| 13:55-14:20 | Mingji Xia. | Maximum Edge-Disjoint Paths Problem in Planar Graphs | 13:55-14:20 | Hiroki Morizumi and Jun Tarui. | Linear-Size Log-Depth Negation-Limited Inverter for $k$-tonic Binary Sequences | |
| 14:20-14:45 | Wang Jiexun, Zhao Liang, Hiroshi Nagamochi and Akutsu Tatsuya. | An Efficient Algorithm for Generating Colored Outerplanar Graphs | 14:20-14:45 | QingShun Zhang and DaoYun Xu. | The Existence of Unsatisfiable Formulas in k-LCNF for k not less than 3 | |
| 14:45-15:10 | Akifumi Kawaguchi and Hiroshi Nagamochi. | Orthogonal Drawings for Plane Graphs with Specified Face Areas | 14:45-15:10 | Xin Li, Tian Liu, Han Peng, Hongtao Sun, Jin Xu, Ke Xu and Jiaqi Zhu. | Improved Exponential Time Lower Bound of Knapsack Problem under BT Model | |
| Short Break | ||||||
| Session 1(Chair:Bjorn Kjos-Hansen ) | Room A | Session 2(Chair: Yijia Chen) | Room B | |||
| 15:25-15:50 | Giordano Fusco and Eric Bach. | Phase Transition of Multivariate Polynomial Systems | 15:25-15:50 | Michael Dom, Jiong Guo and Rolf Niedermeier. | Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems | |
| 15:50-16:15 | Wangsen Feng, Li'ang Zhang, Wanling Qu and Hanpin Wang. | Approximation algorithms for maximum edge coloring problem | 15:50-16:15 | Yunlong Liu, Jianer Chen and Jianxin Wang. | On Efficient FPT Algorithms for Weighted Matching and Packing Problems | |
| 16:15-16:40 | He Sun and Chung Keung Poon. | Two Improved Range-Efficient Estimating Algorithms | 16:15-16:40 | Marc Thurley. | Kernelizations for Parameterized Counting Problems | |
| 16:40-17:05 | Wenbo Zhao. | Approximation to the Minimum Rooted Star Cover Problem | 16:40-17:05 | Xingwu Liu, Zhiwei Xu and Juhua Pu. | Revisiting the Impossibility for Boosting Service Resilience | |
| Short Break | ||||||
| Session 1 (Chair:C.K.Poon) | Room A | Session 2 (Chair: Yunlei Zhao) | Room B | |||
| 17:20-17:45 | Boting Yang and Yi Cao | Directed Searching Digraphs: Monotonicity and Complexity | 17:20-17:45 | Sun-Yuan Hsieh. | Path Embedding on Folded Hypercubes | |
| 17:45-18:10 | Indranil Saha and Debapriyay Mukhopadhyay. | A Distributed Algorithm of Fault Recovery For Stateful Failover | 17:45-18:10 | Jianxin Wang, Xiaoshuang Xu and Jianer Chen. | An Approximation Algorithm based on Chain Implication for Constrained Minimum Vertex Cover in Bipartite Graphs | |
| The End of Conference | ||||||