Quantum computation: through the algorithm and complexity theory lens. This project aims to advance our knowledge of quantum computation through the lens of algorithm and complexity theory. Three core areas of the theory will be examined: interactive computing models, query complexity, and circuit lower bounds. The expected outcomes include: revealing the quantum advantages of interactive computing models; techniques for verifying quantum devices in the cloud and quantum cloud computing in gener ....Quantum computation: through the algorithm and complexity theory lens. This project aims to advance our knowledge of quantum computation through the lens of algorithm and complexity theory. Three core areas of the theory will be examined: interactive computing models, query complexity, and circuit lower bounds. The expected outcomes include: revealing the quantum advantages of interactive computing models; techniques for verifying quantum devices in the cloud and quantum cloud computing in general; sharpening the separation between algorithm performance in quantum and classical query models; establishing both unconditional and conditional hardness results for quantum circuits. This comprehensive understanding will enhance Australia's research portfolio in the theory of quantum computing.Read moreRead less
Faithful Visual Analytics: models, metrics and algorithms. This project aims to deliver new models, metrics and algorithms for Faithful Visual Analytics of complex data. For a purported visual representation of some data, "faithfulness" measures how accurately the visual representation describes the data. This project will develop new models for Faithful Visual Analytics, design new faithfulness metrics for faithful visual analytics of complex networks, design new algorithms to compute faithful ....Faithful Visual Analytics: models, metrics and algorithms. This project aims to deliver new models, metrics and algorithms for Faithful Visual Analytics of complex data. For a purported visual representation of some data, "faithfulness" measures how accurately the visual representation describes the data. This project will develop new models for Faithful Visual Analytics, design new faithfulness metrics for faithful visual analytics of complex networks, design new algorithms to compute faithful visualisations, and evaluate using real world social network and biological network data sets. The new models, metrics and algorithms produced by this project will be used in the next generation Visual Analytic tools to enable analysts develop accurate insights and new knowledge of complex data.Read moreRead less
Tractable topological computing: Escaping the hardness trap. Computational topology is a young and energetic field that uses computers to solve complex geometric problems driven by pure mathematics, and with diverse applications in biology, signal processing and data mining. A major barrier is that many of these problems are thought to be fundamentally and intractably hard. This project aims to defy such barriers for typical real-world inputs by fusing geometric techniques with technologies from ....Tractable topological computing: Escaping the hardness trap. Computational topology is a young and energetic field that uses computers to solve complex geometric problems driven by pure mathematics, and with diverse applications in biology, signal processing and data mining. A major barrier is that many of these problems are thought to be fundamentally and intractably hard. This project aims to defy such barriers for typical real-world inputs by fusing geometric techniques with technologies from the field of parameterised complexity, creating powerful, practical solutions for these problems. It is expected to shed much-needed light on the vast and puzzling gap between theory and practice, and give researchers fast new software tools for large-scale experimentation and cutting-edge computer proofs.Read moreRead less
Devising tools for big data sets to support computational movement analysis. This project aims to devise practical fundamental algorithms and multi-purpose data structures with performance guarantees for big spatio-temporal data sets. Systematic analysis of trajectory data has been occurring since the 1950s, but with the recent technological advances the size of the data sets has recently soared. Existing computational tools were developed for small to mid-size data sets. This project aims to d ....Devising tools for big data sets to support computational movement analysis. This project aims to devise practical fundamental algorithms and multi-purpose data structures with performance guarantees for big spatio-temporal data sets. Systematic analysis of trajectory data has been occurring since the 1950s, but with the recent technological advances the size of the data sets has recently soared. Existing computational tools were developed for small to mid-size data sets. This project aims to devise practical fundamental algorithms that will enable the development of domain specific tools for a wide range of applications, including sports, behavioural ecology, transport, and surveillance.Read moreRead less
Sublinear algorithms for visual analytics of extreme-scale networks. This project aims to design new sublinear algorithms for the visual analytics of extreme-scale networks, involving billions of nodes. Based on algorithmics for graph drawing, integrating sublinear algorithms and distributed algorithms, the project will introduce new quality metrics for good visualisation of extreme-scale networks, design new sublinear-time algorithms to compute good visualisation, implement them in a distribute ....Sublinear algorithms for visual analytics of extreme-scale networks. This project aims to design new sublinear algorithms for the visual analytics of extreme-scale networks, involving billions of nodes. Based on algorithmics for graph drawing, integrating sublinear algorithms and distributed algorithms, the project will introduce new quality metrics for good visualisation of extreme-scale networks, design new sublinear-time algorithms to compute good visualisation, implement them in a distributed computing environment, and evaluate with a real world social network and biological network data sets. The new algorithms produced by this project will be used in the next generation visual analytic tools for extreme-scale data to enable analysts develop new insights and new knowledge of extreme-scale data.Read moreRead less
Trisections, triangulations and the complexity of manifolds. This project aims at practical representations of 3-dimensional and 4-dimensional spaces as needed in applications. Topology is the mathematical study of the shapes of spaces. Geometry endows spaces with additional structure such as distance, angle and curvature. Special combinatorial structures, such as minimal triangulations, are often closely connected to geometric structures or topological properties. This project aims to construct ....Trisections, triangulations and the complexity of manifolds. This project aims at practical representations of 3-dimensional and 4-dimensional spaces as needed in applications. Topology is the mathematical study of the shapes of spaces. Geometry endows spaces with additional structure such as distance, angle and curvature. Special combinatorial structures, such as minimal triangulations, are often closely connected to geometric structures or topological properties. This project aims to construct computable invariants, connectivity results for triangulations, and algorithms to recognise fundamental topological properties and structures such as trisections and bundles.Read moreRead less
Approximate algorithms and architectures for area efficient system design. This project aims to develop simpler but reliable image recognition systems that can run on low-cost, small-scale platforms, for use in driver monitoring system (DMS) applications. Cheaper reliable DMS will lead to wider availability of this technology to end users and improve safety of motor vehicles. This project will develop approximate algorithmic and circuit techniques, provide training for research students and buil ....Approximate algorithms and architectures for area efficient system design. This project aims to develop simpler but reliable image recognition systems that can run on low-cost, small-scale platforms, for use in driver monitoring system (DMS) applications. Cheaper reliable DMS will lead to wider availability of this technology to end users and improve safety of motor vehicles. This project will develop approximate algorithmic and circuit techniques, provide training for research students and build capability in the area of approximate computing. It is also expected to lead to commercial products, licences and revenue, which will enable new job creation.
Read moreRead less
Improved algorithms via random sampling. Randomized methods have recently come into the spotlight when it comes to solving computationally "intractable" subset problems. The running time of a range of algorithms has been improved by replacing their first steps by a simple method of adding to the solution a small subset uniformly at random, and repeating the process many times. This project will explore various other ways how (not necessarily uniform) random sampling can improve the running time ....Improved algorithms via random sampling. Randomized methods have recently come into the spotlight when it comes to solving computationally "intractable" subset problems. The running time of a range of algorithms has been improved by replacing their first steps by a simple method of adding to the solution a small subset uniformly at random, and repeating the process many times. This project will explore various other ways how (not necessarily uniform) random sampling can improve the running time of algorithms; and explore the analysis of polynomial-time randomized algorithms. The project will focus on cycle cutsets and domination problems that have applications in operating systems, chip design and verification, facility location, and surveillance and monitoring.
Read moreRead less