NDLI: Optimal private halfspace counting via discrepancy

Please wait, while we are loading the content...

Faster approximate multicommodity flow using quadratically coupled flows

Quantum money from hidden subspaces

The cell probe complexity of dynamic range counting

Polyhedral clinching auctions and the adwords polytope

Computing a nonnegative matrix factorization -- provably

Short proofs for the determinant identities

Solution of the propeller conjecture in $R^{3}$

From irreducible representations to locally decodable codes

Approximation algorithms for semi-random partitioning problems

Prior-free auctions with ordered bidders

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Fast matrix rank algorithms and applications

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Learning poisson binomial distributions

Competitive contagion in networks

Pseudorandom generators with long stretch and low locality from random local one-way functions

Routing in undirected graphs with constant congestion

Catching the k-NAESAT threshold

Tight bounds for distributed functional monitoring

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

Monotone expansion

Multi-way spectral partitioning and higher-order cheeger inequalities

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

Matroid prophet inequalities

On identity testing of tensors, low-rank recovery and compressed sensing

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space

2log1-ε n hardness for the closest vector problem with preprocessing

Folded codes from function field towers and improved optimal rate list decoding

A near-linear time ε-approximation algorithm for geometric bipartite matching

On the limits of black-box reductions in mechanism design

Tight bounds for monotone switching networks via fourier analysis

Nearly optimal sparse fourier transform

Separating multilinear branching programs and formulas

On vertex sparsifiers with Steiner nodes

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Finding red balloons with split contracts: robustness to individuals' selfishness

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

Improving christofides' algorithm for the s-t path TSP

Complexity of counting CSP with complex weights

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

Rational proofs

Nearly complete graphs decomposable into large induced matchings and their applications

Many sparse cuts via higher eigenvalues

Multiparty computation secure against continual memory leakage

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Span programs for functions with constant-sized 1-certificates: extended abstract

Online matching with concave returns

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

A new point of NP-hardness for unique games

Subspace evasive sets

Using petal-decompositions to build a low stretch spanning tree

Budget feasible mechanism design: from prior-free to bayesian

Interactive information complexity

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

Reconstruction of depth-4 multilinear circuits with top fan-in 2

Approximation algorithms and hardness of integral concurrent flow

Making polynomials robust to noise

An analysis of one-dimensional schelling segregation

Design extractors, non-malleable condensers and privacy amplification

Multiplying matrices faster than coppersmith-winograd

The freezing threshold for k-colourings of a random graph

Tight time-space tradeoff for mutual exclusion

Minimax option pricing meets black-scholes in the limit

Probabilistic existence of rigid combinatorial structures

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Beating randomized response on incoherent matrices

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

Hypercontractivity, sum-of-squares proofs, and their applications

Edge transitive ramanujan graphs and symmetric LDPC good codes

Improved smoothed analysis of multiobjective optimization

An algorithmic characterization of multi-dimensional mechanisms

The multiparty communication complexity of set disjointness

Optimal online buffer scheduling for block devices

Affine projections of polynomials: extended abstract

Robust satisfiability of constraint satisfaction problems

A tight RMR lower bound for randomized mutual exclusion

A quantitative gibbard-satterthwaite theorem without neutrality

From query complexity to computational complexity

Matroids and integrality gaps for hypergraphic steiner tree relaxations

Unconditional differentially private mechanisms for linear queries

Strict fibonacci heaps

Optimal private halfspace counting via discrepancy

Tight lower bounds for the online labeling problem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

Optimal private halfspace counting via discrepancy

Content Provider	ACM Digital Library
Author	Muthukrishnan, S. Nikolov, Aleksandar
Abstract	A range counting problem is specified by a set P of size \|P\| = n of points in $R^{d},$ an integer weight $x_{p}$ associated to each point p ∈ P, and a range space R ⊆ $2^{P}.$ Given a query range R ∈ R, the output is R(x) = ∑p ∈ $R}x_{p}.$ The average squared error of an algorithm A is 1/\|R\|∑R ∈ R((A(R, x) - $R(x)))^{2}.$ Range counting for different range spaces is a central problem in Computational Geometry. We study (ε, δ)-differentially private algorithms for range counting. Our main results are for the range space given by hyperplanes, that is, the halfspace counting problem. We present an (ε, δ)-differentially private algorithm for halfspace counting in d dimensions which is $O(n^{1-1/d})$ approximate for average squared error. This contrasts with the Ω(n) lower bound established by the classical result of Dinur and Nissim on approximation for arbitrary subset counting queries. We also show a matching lower bound of $Ω(n^{1-1/d})$ approximation for any (ε, δ)-differentially private algorithm for halfspace counting. Both bounds are obtained using discrepancy theory. For the lower bound, we use a modified discrepancy measure and bound approximation of (ε, δ)-differentially private algorithms for range counting queries in terms of this discrepancy. We also relate the modified discrepancy measure to classical combinatorial discrepancy, which allows us to exploit known discrepancy lower bounds. This approach also yields a lower bound of Ω((log $n)^{d-1})$ for (ε, δ)-differentially private orthogonal range counting in d dimensions, the first known superconstant lower bound for this problem. For the upper bound, we use an approach inspired by partial coloring methods for proving discrepancy upper bounds, and obtain (ε, δ)-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.
Starting Page	1285
Ending Page	1292
Page Count	8
File Format	PDF MP4
ISBN	9781450312455
DOI	10.1145/2213977.2214090
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Differential privacy Range counting Combinatorial discrepancy
Content Type	Audio Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in