SACT: Sydney algorithms and computing theory

Time: 1:00pm Tuesday, 31st May 2016. Location: SIT 459 Speaker: Natalie Tridgell, University of Sydney Title: Cartesian Tree of Tree Algorithms Abstract: We study the problem of constructing a cartesian tree of a tree. We present two new algorithms for computing a cartesian tree of a tree. We will look at worst case scenarios for … Continue reading

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

The ARC has published the outcomes of the latest Excellence in Research for Australia (ERA) ranking. The University of Sydney was ranked “well above world standard” in Computation Theory and Mathematics (0802), the highest possible ranking!