Quentin Hillebrand

Quentin Hillebrand

Auto-generated profile, based on publicly available information

Quentin Hillebrand

The University of Tokyo Tokyo Japan

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 August 2023
Verified
Conference Paper
Open access
QHQuentin Hillebrand
Quentin Hillebrand
VSVorapong Suppakitpaisarn
Vorapong Suppakitpaisarn
TSTetsuo Shibuya
Tetsuo Shibuya
This work presents a mechanism to debias polynomial functions computed from locally differentially private data. Local differential privacy is a widely used privacy notion where users add Laplacian noise to their information before submitting it to a central server. That, however, causes bias when we calculate non-linear functions based on those noisy information. Our proposed recursive algorithm debiases these functions, with a calculation time of O(r n log n), where r is the polynomial degree and n is the number of users. We evaluate our method on the problems of k-star counting and variance estimation, comparing results with state-of-the-art algorithms. The results show that our method not only eliminates bias, but also provides at least 100 times more accuracy than previous works.

18 June 2025 in arXiv
Verified
Preprint
Open access
PDF file
KPKevin Pfisterer
Kevin Pfisterer
QHQuentin Hillebrand
Quentin Hillebrand
VSVorapong Suppakitpaisarn
Vorapong Suppakitpaisarn
In this paper, we introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP). Under this model, we ensure the privacy of client presence at specific locations. When n is the number of points, Gupta et al. established a lower bound of $Ω(\sqrt{n})$ on the approximation ratio for any differentially private algorithm applied to the original facility location problem. As a result, subsequent works have adopted the super-set assumption, which may, however, compromise user privacy. We show that this lower bound does not apply to our adaptation by presenting an LDP algorithm that achieves a constant approximation ratio with a relatively small additive factor. Additionally, we provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.


4 June 2026
Verified
Conference Paper
Open access
QHQuentin Hillebrand
Quentin Hillebrand
VSVorapong Suppakitpaisarn
Vorapong Suppakitpaisarn
TSTetsuo Shibuya
Tetsuo Shibuya
We present a method for privately publishing sparse vectors with communication and computation costs that scale linearly with the number of nonzero elements. The Poisson Private Representation (PPR) framework was introduced to compress any differentially private mechanism to achieve a communication cost of O(ϵ), where ϵ is the privacy budget. However, PPR and its variant, Chunk PPR, are not well suited for publishing sparse vectors under metric differential privacy: PPR incurs exponential computation cost, while Chunk PPR requires both execution and communication costs linear in the vector dimension. As a result, their guarantees are no stronger than those of non-compressed randomized response, which for a matrix with N users, n columns, and m nonzero elements, requires Ω(nN) communication—rendering it impractical for large-scale data. Our PPR-based algorithm overcomes these limitations, reducing communication to O (ϵm). Remarkably, this is even lower than the non-private baseline, which needs Ω(m log n) bits. Furthermore, as the privacy budget decreases, communication cost is further reduced, enabling stronger privacy with greater efficiency We provide theoretical guarantees showing that our method yields results equivalent to randomized response, and experimental evaluations confirm its advantages in accuracy, communication efficiency, and computational complexity. Finally, we demonstrate its applicability across domains such as social-network adjacency matrices, user-item interaction matrices in recommender systems, and single-nucleotide polymorphism (SNP) profiles in genomic data.

25 June 2025 in arXiv
Verified
Preprint
Open access
PDF file
QHQuentin Hillebrand
Quentin Hillebrand
VSVorapong Suppakitpaisarn
Vorapong Suppakitpaisarn
TSTetsuo Shibuya
Tetsuo Shibuya
In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with $N$ users, $n$ columns, and $m$ nonzero elements, conventional methods require $Ω(n \times N)$ communication, making them impractical for large-scale data. Our algorithm significantly reduces this cost to $O(\varepsilon m)$, where $\varepsilon$ is the privacy budget. Notably, this is even lower than the non-private case, which requires $Ω(m \log n)$ communication. Moreover, as the privacy budget decreases, communication cost further reduces, enabling better privacy with improved efficiency. We theoretically prove that our method yields results identical to those of randomized response, and experimental evaluations confirm its effectiveness in terms of accuracy, communication efficiency, and computational complexity.