|
Saturday,
December 15, 2012
|
|
8:00 - 8:45
|
Registration [SH-1]
|
|
8:45 - 9:00
|
Inauguration and welcome address [SH-1]
|
|
9:00 - 10:00
|
Invited Talk [SH-1]
Yuval Rabani, Learning Mixtures of
Distributions over Large Discrete Domains
Chair: Jaikumar Radhakrishnan
|
|
10:00 - 10:30
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
10:30 - 12:30
|
Session 1A: Complexity [SH-1]
Chair: Jaikumar Radhakrishnan
|
Session 1B: Logic and Games [B6-309]
Chair: Madhavan Mukund
|
|
|
Swastik Kopparty and Srikanth Srinivasan, Certifying polynomials for AC^0(parity) circuits, with applications
|
Andreas Krebs and Howard Straubing, An effective characterization of the alternation hierarchy in two-variable logic
|
|
Santosh Vempala, Randomly-Oriented k-d Trees Adapt to Intrinsic Dimension
|
Vince Barany, Mikołaj Bojańczyk, Diego Figueira and Pawel Parys, Decidable classes of documents for XPath
|
|
Navin Goyal and Luis Rademacher,
Lower Bounds for the Average and Smoothed Number of Pareto Optima |
Jakub Gajarsky and Petr Hlineny, Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
|
|
Venkatesan Chakaravarthy, Natwar Modani, Sivaramakrishnan Natarajan,
Sambuddha Roy and Yogish Sabharwal,
Density Functions subject to a Co-Matroid Constraint
|
Nathanael Fijalkow and Martin Zimmermann, Cost-Parity and Cost-Streett Games
|
|
12:30 - 14:00
|
Lunch Break [Guest House]
|
|
14:00 - 15:00
|
Invited Talk [SH-1]
Madhusudan Parthasarathy, Automated Reasoning and Natural Proofs for Programs Manipulating Data Structures
Chair: K. Narayan Kumar
|
|
15:00 - 15:10
|
Short Break
|
|
15:10 - 16:10
|
Session 2A: Distributed Models [SH-1]
Chair: Sourav Chakraborty
|
Session 2B: Pushdown Automata [B6-309]
Chair: Anil Seth
|
|
|
Kishore Kothapalli and Sriram Pemmaraju,
Super-Fast 3-Ruling Sets
|
Christopher Broadbent and Stefan Göller, On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
|
|
Gabor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha and Ronald de Wolf,
New bounds on the classical and quantum communication complexity
of some graph properties
|
Salvatore La Torre and Gennaro Parlato,
Scope-bounded Multistack Pushdown Systems: Fixed-Point, Sequentialization, and Tree-Width
|
|
16:10 - 16:40
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
16:40 - 17:40
|
Session 3A: Scheduling [SH-1]
Chair: Sourav Chakraborty
|
Session 3B: Automata [B6-309]
Chair: Supratik Chakraborty
|
|
|
Rohit Khandekar, Kirsten Hildrum, Deepak Rajan and Joel Wolf, Scheduling with
Setup Costs and Monotone Penalties
|
Laura Bozzelli and Cesar Sanchez,
Visibly Rational Expressions
|
|
Venkatesan Chakaravarthy, Arindam Pal, Sambuddha Roy and Yogish Sabharwal, Scheduling
Resources for Executing a Partial Set of
Jobs
|
Alexander Heußner, Tristan Le Gall and
Grégoire Sutre,
Safety Verification of Communicating One-Counter Machines
|
|
17:45 - 18:30
|
Business Meeting [B6-309]
|
|
|
|
Sunday,
December 16, 2012
|
|
9:00 - 10:00
|
Invited Talk [SH-1]
Mikołaj Bojańczyk, Imperative Programming in Sets with Atoms
Chair: Kamal Lodaya
|
|
10:00 - 10:30
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
10:30 - 12:30
|
Session 4A: Approximation Algorithms [SH-1]
Chair: Kavitha Telikepalli
|
Session 4B: Rewriting and Reachability [B6-309]
Chair: Sanjiva Prasad
|
|
|
Guy Feigenblat, Ely Porat and Ariel Shiftan, Exponential Space Improvement for minwise Based Algorithms
|
Jonathan Hayman, Vincent Danos, Jérôme Feret, Walter Fontana, Russell Harmer, Jean Krivine, Chris Thompson-Walsh and Glynn Winskel, Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models
|
|
Amit Kumar, Preeti Panda and Smruti Sarangi,
Efficient on-line algorithms for maintaining k-cover of sparse bit-strings
|
Riccardo Traverso, Giorgio Delzanno, Arnaud Sangnier and Gianluigi Zavattaro, On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks
|
|
Abhash Anand, Surender Baswana, Manoj Gupta and Sandeep Sen, Maintaining
Approximate Maximum Weighted Matching in
Fully Dynamic Graphs
|
Remi Bonnet, Alain Finkel and M. Praveen, Extending the Rackoff technique to Affine nets
|
|
Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula and Arindam Pal, Approximation
Algorithms for the Unsplittable Flow
Problem on Paths and Trees
|
Anthony Widjaja Lin, Accelerating tree-automatic relations
|
|
12:30 - 14:00
|
Lunch Break [Guest House]
|
|
14:00 - 15:00
|
Invited Talk [SH-1]
Dimitris Achlioptas, Randomness in Networks: can less be more?
Chair: Amit Deshpande
|
|
15:00 - 15:10
|
Short Break
|
|
15:10 - 16:40
|
Session 5A: Path Computation [SH-1]
Chair: Amit Deshpande
|
Session 5B: Timed and Quantitative Systems [B6-309]
Chair: Aditya Kanade
|
|
|
Binay Bhattacharya and Yuzhuang Hu, k-Delivery traveling salesman problem on tree networks
|
Udi Boker and Thomas Henzinger, Approximate Determinization of Quantitative Automata
|
|
Paul Bonsma, Rerouting
shortest paths in planar graphs
|
Jonathan Cederberg, Parosh Aziz Abdulla and Mohamed Faouzi Atig, Timed Lossy Channel Systems
|
|
Varun Rajan, Space Efficient Edge Fault Tolerant Routing
|
|
|
16:30 - 17:00
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
18:00 - 19:30
|
Cultural Event
|
|
19:30 - 22:00
|
Conference Banquet [Venue]
|
|
|
|
Monday, December 17, 2012
|
|
9:00 - 10:00
|
Invited Talk [SH-1]
Patrice Godefroid, Test Generation Using Symbolic Execution
Chair: Deepak D'Souza
|
|
10:00 - 10:30
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
10:30 - 12:30
|
Session 6A: Graph Algorithms [SH-1]
Chair: Kishore Kothapalli
|
Session 6B: Probabalistic Automata [B6-309]
Chair: Parosh Aziz Abdulla
|
|
|
Johannes Köbler, Sebastian Kuhnert and Oleg Verbitsky,
Solving the Canonical
Representation and Star System Problems
for Proper Circular-Arc Graphs in Logspace
|
Andrea Turrini and Holger Hermanns,
Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
|
|
Robert Crowston, Gregory Gutin and Mark Jones, Directed Acyclic Subgraph Problem Parameterized above Raman-Saurabh Bound
|
Vojtech Forejt, Petr Jancar, Stefan Kiefer and James Worrell, Bisimilarity of Probabilistic Pushdown Automata
|
|
Matthias Mnich, Geevarghese Philip, Saket Saurabh and Ondrej Suchy, Beyond Max-Cut:
Lambda-Extendible
Properties Parameterized Above the Poljak-Turzík Bound
|
Krishnendu Chatterjee, Manas Joglekar and Nisarg Shah, Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Buchi Objectives
|
|
Daniel Lokshtanov, Saket Saurabh and Magnus Wahlström, Subexponential Parameterized Odd Cycle Transversal on Planar Graphs
|
Tomas Brazdil, Holger Hermanns, Jan Krcal, Jan Kretinsky and Vojtech Rehak, Verification of Open Interactive Markov Chains
|
|
12:30 - 14:00
|
Lunch Break [Guest House]
|
|
14:00 - 15:30
|
Session 7A: Geometry [SH-1]
Chair: Rahul Jain
|
Session 7B: Program Analysis and
Security [B6-309]
Chair: Nishant Sinha
|
|
|
Kasturi Varadarajan and Xin Xiao, On the
Sensitivity of Shape Fitting Problems
|
Pranavadatta Devaki and Aditya Kanade, Static Analysis for Checking Data Format Compatibility of Programs
|
|
Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon and Juyoung Yon, Overlap of
Convex Polytopes under Rigid Motion
|
Rohit Chadha and Michael Ummels, The Complexity of Quantitative Information Flow in Recursive Programs
|
|
Minati De, Subhas Nandy and Sasanka Roy, Minimum Enclosing Circle with Few Extra Variables
|
Gergei Bana, Pedro Adao and Hideki Sakurada, Computationally Complete Symbolic Attacker in Action
|
|
15:30 - 15:40
|
Closing Remarks [SH-1]
|
|
15:40 - 16:10
|
Tea/Coffee Break [Inbetween SH-1 and B6-309]
|
|
END
OF CONFERENCE
|
