Oxford papers for ICALP-2015

Nine Oxford papers have been accepted to the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). The ICALP conference, held from 6-10 July in Kyoto, Japan, is an annual international forum on various aspects of theoretical computer science. For more information, visit http://www.kurims.kyoto-u.ac.jp/icalp2015/.

The nine papers, authored or co-authored by members of the department are: 

Track A: Algorithms, Complexity and Games

• Peter Fulla and Stanislav Zivny: A Galois connection for valued constraint languages of infinite size
• Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum: Approximately Counting H-Colourings is #BIS-Hard
• Andreas Göbel, Leslie Ann Goldberg and David Richerby: Counting Homomorphisms to Square-Free Graphs, Modulo 2
• Leslie Ann Goldberg, Rob Gysel and John Lapinskas: Approximately counting locally-optimal structures
• Johan Thapper and Stanislav Zivny: Sherali-Adams relaxations for valued CSPs

Track B: Logic, Semantics, Automata and Theory of Programming

• Samson Abramsky, Radha Jagadeesan and Matthijs Vákár: Games for Dependent Types
• Christoph Haase and Stefan Kiefer: The Odds of Staying on Budget
• Sam Staton and Sander Uijlen: Effect algebras, presheaves, non-locality and contextuality

Track C: Foundations of Networked Computation: Models, Algorithms and Information Management

• Yiannis Giannakopoulos and Elias Koutsoupias: Selling Two Goods Optimally.