ORCID Profile
0000-0001-7153-5211
Current Organisation
University of Sydney
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
In Research Link Australia (RLA), "Research Topics" refer to ANZSRC FOR and SEO codes. These topics are either sourced from ANZSRC FOR and SEO codes listed in researchers' related grants or generated by a large language model (LLM) based on their publications.
Data structures and algorithms | Data and information privacy | Theory of computation |
Publisher: Center for Open Science
Date: 11-12-2017
Abstract: In order to study the real world, scientists (and computer scientists) develop simplified models that attempt to capture the essential features of the observed system. Understanding the power and limitations of these models, when they apply or fail to fully capture the situation at hand, is therefore of uttermost importance.In this thesis, we investigate the role of some of these models in property testing of probability distributions (distribution testing), as well as in related areas. We introduce natural extensions of the standard model (which only allows access to independent draws from the underlying distribution), in order to circumvent some of its limitations or draw new insights about the problems they aim at capturing. Our results are organized in three main directions: (i) We provide systematic approaches to tackle distribution testing questions. Specifically, we provide two general algorithmic frameworks that apply to a wide range of properties, and yield efficient and near-optimal results for many of them. We complement these by introducing two methodologies to prove information-theoretic lower bounds in distribution testing, which enable us to derive hardness results in a clean and unified way. (ii) We introduce and investigate two new models of access to the unknown distributions, which both generalize the standard s ling model in different ways and allow testing algorithms to achieve significantly better efficiency. Our study of the power and limitations of algorithms in these models shows how these could lead to faster algorithms in practical situations, and yields a better understanding of the underlying bottlenecks in the standard s ling setting. (iii) We then leave the field of distribution testing to explore areas adjacent to property testing. We define a new algorithmic primitive of s ling correction, which in some sense lies in between distribution learning and testing and aims to capture settings where data originates from imperfect or noisy sources. Our work sets out to model these situations in a rigorous and abstracted way, in order to enable the development of systematic methods to address these issues.
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 05-2020
Publisher: Journal of Privacy and Confidentiality
Date: 29-07-2022
DOI: 10.29012/JPC.784
Abstract: A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Unfortunately, using a continuous distribution presents several practical challenges. First and foremost, finite computers cannot exactly represent s les from continuous distributions, and previous work has demonstrated that seemingly innocuous numerical errors can entirely destroy privacy. Moreover, when the underlying data is itself discrete (e.g., population counts), adding continuous noise makes the result less interpretable. With these shortcomings in mind, we introduce and analyze the discrete Gaussian in the context of differential privacy. Specifically, we theoretically and experimentally show that adding discrete Gaussian noise provides essentially the same privacy and accuracy guarantees as the addition of continuous Gaussian noise. We also present an simple and efficient algorithm for exact s ling from this distribution. This demonstrates its applicability for privately answering counting queries, or more generally, low-sensitivity integer-valued queries.
Publisher: Now Publishers
Date: 2022
DOI: 10.1561/0100000114
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2023
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 10-2017
Publisher: Society for Industrial & Applied Mathematics (SIAM)
Date: 2018
DOI: 10.1137/16M1076666
Publisher: Association for Computing Machinery (ACM)
Date: 11-02-2019
DOI: 10.1145/3305270
Abstract: We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds. Our main result is concerned with testing identity to a specific distribution, p , given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the s le complexity of the aforementioned problem is closely related to the ℓ 2/3 -quasinorm of p . We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the s le complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre’s K-functional . We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p ). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.
Publisher: Theory of Computing Exchange
Date: 2019
Publisher: Springer Science and Business Media LLC
Date: 24-05-2018
Publisher: Society for Industrial and Applied Mathematics
Date: 18-12-2014
Publisher: Association for Computing Machinery (ACM)
Date: 22-07-2019
DOI: 10.1145/3337789
Abstract: A function f :{ −1,1} n → { −1,1} is a k -junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k -juntas, where the testing algorithm must accept any function that is ε- close to some k -junta and reject any function that is ε′-far from every k ′-junta for some ε′ = O (ε) and k ′ = O ( k ). Our first result is an algorithm that solves this problem with query complexity polynomial in k and 1/ε. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function. Our second result considers the case where k ′ = k . We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that, given ρ ∈ (0,1), accepts any function that is ε ρ/16-close to some k -junta and rejects any function that is ε-far from every k -junta. The query complexity of the algorithm is O ( k log k /ε ρ (1-ρ) k . Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions f and g . We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest k such that either f or g is close to being a k -junta.
Publisher: Theory of Computing Exchange
Date: 2018
Publisher: ACM
Date: 18-06-2023
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 12-2020
Publisher: Springer Science and Business Media LLC
Date: 20-06-2018
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2022
Publisher: Theory of Computing Exchange
Date: 2020
Publisher: IEEE
Date: 06-2015
Publisher: Society for Industrial & Applied Mathematics (SIAM)
Date: 2015
DOI: 10.1137/130945508
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 12-2020
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 03-2021
Start Date: 2023
End Date: 12-2025
Amount: $432,355.00
Summary: Trading Privacy, Bandwidth and Accuracy in Algorithmic Machine Learning. This project aims to investigate the trade-offs between privacy, communication costs and accuracy of results when learning from users' sensitive data. The project intends to design faster and more accurate algorithms for a wide range of machine learning tasks by developing a novel and widely-applicable algorithmic framework. Expected outcomes of this project include new theoretical tools to guide the design of data-driven d .... Trading Privacy, Bandwidth and Accuracy in Algorithmic Machine Learning. This project aims to investigate the trade-offs between privacy, communication costs and accuracy of results when learning from users' sensitive data. The project intends to design faster and more accurate algorithms for a wide range of machine learning tasks by developing a novel and widely-applicable algorithmic framework. Expected outcomes of this project include new theoretical tools to guide the design of data-driven decision systems and rigorously analyse their performance and privacy guarantees. Privacy of individuals' information in data analytics pipelines is a key societal concern. This project should lead to significant benefits by strengthening privacy in these pipelines while also improving accuracy and cost-efficiency. Read more Read less
Funder: Australian Research Council
View Funded Activity