SACT: Sydney algorithms and computing theory

Time: 1:00pm Tuesday, 17th May 2016. Location: SIT 459 Speaker: Michael Horton, University of Sydney Title: Compact Flow Diagrams for State Sequences Abstract: We introduce the concept of compactly representing a large number of state sequences, e.g., sequences of activities, as a flow diagram. We argue that the flow diagram representation gives an intuitive summary … Continue reading

Time: 1:00pm Tuesday, 3rd May 2016. Location: SIT 459 Speaker: Simon Mackenzie, Data61 Title: A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents Abstract: We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from the agents. The problem has received … Continue reading

Time: 1:00pm Tuesday, 19th April 2016. Location: SIT 459 Speaker: Julian Mestre, University of Sydney Title: Scheduling problems in synchronous data flow programming Abstract: We study a scheduling problem arising in the execution of synchronous data flow programs. We propose three objective functions capturing the memory usage of a program under different memory management schemes. … Continue reading

Time: 1:00pm Tuesday, 5th April 2016. Location: SIT 459 Speaker: Serge Gaspers, UNSW / Data61 Title: Exact Algorithms via Monotone Local Search Abstract: We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n … Continue reading

Time: 1:00pm Tuesday, 22nd March. Location: SIT 459 Speaker: Youming Qiao, UTS Title: Quantum matching problems Abstract: We describe two algorithmic problems, both of which can be viewed as quantum analogues of the perfect matching problem on bipartite graphs. Given several square matrices, we are asked to: (1) decide if there is a full-rank matrix in … Continue reading

Time: 1:30pm Tuesday, 15th March. Location: SIT 459 Speaker: Nicholas Mattei, Data61/UNSW Title: A Novel Strategyproof Peer Selection Mechanism Abstract: There are many important settings where a group of agents want to select some subset of themselves, crowdsourcing the selection. For example, scientists might want to select some subset to fund, or a community might … Continue reading

Time: 1:30pm Tuesday, 1st March. Location: SIT 459 Speaker: Ronald de Haan, TU Wien, Austria Title: Parameterized Complexity of Problems in the Polynomial Hierarchy Abstract: Parameterized complexity provides a theoretical framework that allows for an analysis of the complexity of problems where structure that is present in the input can be taken into account. This … Continue reading

Time: 1:30pm Tuesday, 23rd February. Location: SIT 459 Speaker: David Avis, Kyoto University Title: Extension Complexity An overview of extension complexity up to Rothvoss’ result that the matching polytope has exponential extension complexity, then two avenues to move forward. (a) H-free extension complexity which allows certain ‘easy’ constraints to be ignored. (b) An explicit construction … Continue reading