Entropy, optimization and counting
From MaRDI portal
Abstract: In this paper we study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. Interest in such distributions arises due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and, more recently, approximation algorithms. A key difficulty in computing max-entropy distributions has been to show that they have polynomially-sized descriptions. We show that such descriptions exist under general conditions. Subsequently, we show how algorithms for (approximately) counting the underlying discrete set can be translated into efficient algorithms to (approximately) compute max-entropy distributions. In the reverse direction, we show how access to algorithms that compute max-entropy distributions can be used to count, which establishes an equivalence between counting and computing max-entropy distributions.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(20)- Maximum entropy and integer partitions
- On geodesically convex formulations for the Brascamp-Lieb constant
- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- On the computability of continuous maximum entropy distributions with applications
- Optimization, complexity and invariant theory (invited talk)
- Computational implications of reducing data to sufficient statistics
- Efficiently list‐edge coloring multigraphs asymptotically optimally
- Maximum Entropy Distributions with Applications to Graph Simulation
- Random weighting, asymptotic counting, and inverse isoperimetry
- Complexity of robust orbit problems for torus actions and the abc-conjecture
- Minimizing the determinant of the graph Laplacian
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Random walks in polytopes and negative dependence
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- On a probabilistic approach to synthesize control policies from example datasets
- Combinatorial Bernoulli factories
- Generalized maximum entropy estimation
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- On the complexity of computing maximum entropy for Markovian models
- Contention resolution, matrix scaling and fair allocation
This page was built for publication: Entropy, optimization and counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259538)
