Session 1

Algorithms

(Minghui Jiang)

8:30 - 8:50

028: Derandomizing HSSW Algorithm for 3-SAT, Kazuhisa Makino, Suguru Tamaki, and Masaki Yamamoto.

8:50 - 9:10

054: Dominating Set Counting in Graph Classes, Shuji Kijima, Yoshio Okamoto, and Takeaki Uno

9:10 - 9:30

022: The Density Maximization Problem in Graphs, Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, and Dorothea Wagner.

9:30 - 9:50

082: FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time, Malte Brinkmeyer, Thasso Griebel, and Sebastian Böcker.

9:50 - 10:10

004: Tight Bounds on Local Search to Approximate The Maximum Satisfiability Problems, Daming Zhu, and Shaohan Ma.

Coffee Break

10:10 - 10:20

Coffee Break

Session 2

Parameterized Algorithms

(Gianluca De Marco)

10:20- 10:40

019: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy, Minghui Jiang and Yong Zhang.

10:40 - 11:00

049: Exact Parameterized Multilinear Monomial Counting via k-layers Subset Convolution and k-Disjoint Sum, Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, and Francis C.M. Lau.

11:00 - 11:20

077: On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms, Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou.

11:20 - 11:40

090: On Parameterized Independent Feedback Vertex Set, Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh.

11:40 - 12:00

093: Cograph Editing: Complexity and Parameterized Algorithms,  Yunlong Liu, Jianxin Wang, Jiong Guo, and Jianer Chen. 

Lunch Time

12:00 - 13:30

Lunch Period

Session 3

Computational Complexity Theory

(Jianer  Chen)

13:30 - 13:50

032: Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems, Tomoyuki Yamakami.

13:50 - 14:10

067: Strong I/O Lower Bounds for Binomial and FFT Computation Graphs, Desh Ranjan, John Savage, and Mohammad Zubair.

14:10 - 14:30

114: Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities, Jin-Yi Cai and Michael Kowalczyk.

14:30 - 14:50

116: Quantum Algorithm for the Boolean Hidden Shift Problem, Dmitry Gavinsky, Martin Roetteler, and Jérémie Roland.

14:50 - 15:10

107: A Kolmogorov Complexity Proof of the Lovász Local Lemma,
Jochen Messner andThomas Thierauf.

Coffee Break

15:20 - 15:30

Coffee Break

Session 4

Geometric Algorithms

(A.  Pavan)

15:30 - 15:50

007: Proper n-Cell Polycubes in n-3 Dimensions,  Andrei Asinowski, Gill Barequet, Ronnie Barequet, and Günter Rote.

15:50 - 16:10

027: Largest Area Convex Hull of Axis-aligned Squares, Ovidiu Daescu, Wenqi Ju, Jun Luo, and Binhai Zhu.

16:10 - 16:30

097: Improved Algorithms for the Point-Set Embeddability problem for Plane 3-Trees, Tanaeem M Moosa and M. Sohel Rahman.

16:30 - 16:50

128: Optimal Strategies for the One-Round Discrete Voronoi Game on a Line, Aritra Banik, Bhaswar B. Bhattacharya, and Sandip Das.

16:50 - 17:10

035: Computing the Girth of a Planar Graph in Linear Time,  Hsien-Chih Chang, and Hsueh-I Lu

Keynote Session

(Bin Fu)

Session 5
Complexity Theory
(Desh Ranjan)

9:30 - 9:50

108: Unions of Disjoint NP-complete Sets, Christian Glaßer, John Hitchcocky, A. Pavanz, and Stephen Travers.

9:50 - 10:10

102: ReachFewL = ReachUL,  Tewari, Raghunath; Vinodchandran, N. V.; Stolee, Derrick; Garvin, and Brady.

Coffee Break

10:10 - 10:20

Coffee Break

Session 6

Approximation Algorithms 

(Ryan Williams)

10:20 - 10:40

017: (1+ε)-Competitive Algorithm for Online OVSF Code Assignment with Resource Augmentation, Yuichi Asahiro, Kenta Kanmera, and  Eiji Miyano.

10:40 - 11:00

098: Scheduling Jobs on Heterogeneous Platforms, Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram.

11:00 - 11:20

115: Self-Assembling Rulers for Approximating Generalized Sierpinski Carpets, Steven M. Kautz and Brad Shutters.

11:20 - 11:40

011: Approximately Uniform Online Checkpointing, Lauri Ahlroth, Olli Pottonen, and André Schumacher.

Lunch Time

12:00 - 13:30

Lunch Period

Session 7

Graph Algorithms

(Minghui  Jiang)

13:30 - 13:50

003: Bandwidth of Convex Bipartite Graphs and Related Graph Classes, Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno.

13:50 - 14:10

044: Algorithms for Partition of Some Class of Graphs under Compaction,  Narayan Vikas.

14:10 - 14:30

076: A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition, Binh-Minh Bui-Xuan, Pinar Heggernes, Ross McConnell, Daniel Meister, and Andrzej Proskurowski.

14:30 - 14:50

080: Matching and P_2-Packing: Weighted Versions,  Qilong Feng, Jianxin Wang, Jianer Che.

14:50 - 15:10

091: On Totally Unimodularity of Edge-Edge Adjacency Matrices,  Yusuke Matsumoto, Naoyuki Kamiyama, and Keiko Imai.

Coffee Break

15:20 - 15:30

Coffee Break

Session 8

Networking Algorithms

(Vikraman Arvind)

15:30 - 15:50

026: The Topology Aware File Distribution Problem,  Shawn T. O'Neil, Amitabh Chaudhary, Danny Z. Chen, and Haitao Wang.

15:50 - 16:10

106: Exploiting the Robustness on Power-Law Networks, Yilin Shen, Nam P. Nguyen, My T. Thai.

16:10 - 16:30

132: Online Pricing for Identical Items, Yong Zhang, Francis Y.L. Chin, and Hing-Fung Ting.

16:30 - 16:50

16:50 - 17:10

056: An Integer Programming Approach for the Rural Postman Problem with Time Dependent Travel Times,  Guozhen Tan and Jinghao Sun.

Banquet

Banquet

Session 9

Algebraic Computation 

(Michael Kowalczyk)

8:30 - 8:50

040: Property Testing for Cyclic Groups and Beyond, Francois Le Gall and Yuichi Yoshida.

8:50 - 9:10

9:10 - 9:30

081: Linear Time Algorithms for the Basis of Abelian Groups, Gregory Karagiorgos and Dimitrios Poulakis.

9:30 - 9:50

068: Characterizations of Locally Testable Linear- and Affine-invariant Families, Angsheng Li, and Yicheng Pan.

9:50 - 10:10

Coffee Break

10:10 - 10:20

Coffee Break

Session 10

  Computational Biology 

(Kaz Makino)

10:20 - 10:40

031: On the Right-seed Array of a String,  Michalis Christou, Maxime Crochemore, Ondrej Guth, Costas S. Iliopoulos,  and Solon P. Pissis.

10:40 - 11:00

042: Compressed Directed Acyclic Word Graph with application in Local Alignment,  Do Huy Hoang and Sung Wing Kin. 

11:00 - 11:20

020: Unavoidable Regularities in Long Words with Bounded Number of Symbol Occurrences,  Juha Kortelainen, Tuomas Kortelainen, and Ari Vesanen.

11:20 - 11:40

047: Summing Symbols in Mutual Recurrences, Berkeley R. Churchill and Edmund A. Lamagna.

11:40 - 12:00

113: Flipping Triangles and Rectangles, Minghui Jiang.

Lunch Time

12:00 - 13:30

Lunch Period

Session 11

Miscellaneous algorithms

(Zaixin Lu)

13:30 - 13:50

103: Unconstrained and Constrained Fault-Tolerant Resource Allocation Problems, Kewen Liao and Hong Shen.

13:50 - 14:10

117: Finding Paths with Minimum Shared Edges, Masoud T. Omran,  Jörg-Rüdiger Sack, and Hamid Zarrabi-Zadeh.

14:10 - 14:30

131: Combinatorial Group Testing for Corruption Localizing Hashing, Annalisa De Bonis and Giovanni Di Crescenzo.

14:30 - 14:50

094: Task Ordering and Memory Management Problem for Degree of Parallelism Estimation, Sergiu Carpov, Jacques Carlier, Dritan Nace, and Renaud Sirdey.

14:50 - 15:10

089: Computing Majority with Triple Queries, Gianluca De Marco, Evangelos Kranakis, and Gabor Wiener.

15:20 - 15:30

Session 12
Miscellaneous algorithms
(Evangelos Kranakis)

15:30 - 15:50

074: A New Variation of Hat Guessing Games, Tengyu Ma, Xiaoming Sun, and Huacheng Yu.

15:50 - 16:10

16:10 - 16:30

070: Optimal Online Algorithms on Two Hierarchical Machines with Resource Augmentation, Yiwei Jiang and An Zhang.