10 citations · 16 across the 7 of their papers we have counts for
7 papers
A Simple Algorithm for Graph Reconstruction
Claire Mathieu, Hang Zhou
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goa…
A PTAS for Capacitated Vehicle Routing on Trees
Claire Mathieu, Hang Zhou
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result…
Optimization of Bootstrapping in Circuits
Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu +1
In 2009, Gentry proposed the first Fully Homomorphic Encryption (FHE) scheme, an extremely powerful cryptographic primitive that enables to perform computations, i.e., to evaluate…
Near-Linear Query Complexity for Graph Inference
Sampath Kannan, Claire Mathieu, Hang Zhou
How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let be an unweighted, connected graph of bounded degree. The…
Graph Reconstruction via Distance Oracles
Claire Mathieu, Hang Zhou
We study the problem of reconstructing a hidden graph given access to a distance oracle. We design randomized algorithms for the following problems: reconstruction of a degree boun…
Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs
Marc Lelarge, Hang Zhou
For a graph , let be the partition function of the monomer-dimer system defined by , where is the number of matchings of size in . We…
Approximation for Maximum Surjective Constraint Satisfaction Problems
Walter Bach, Hang Zhou
Maximum surjective constraint satisfaction problems (Max-Sur-CSPs) are computational problems where we are given a set of variables denoting values from a finite domain B and a set…