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
- 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
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- 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
(23)- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- On a probabilistic approach to synthesize control policies from example datasets
- Contention resolution, matrix scaling and fair allocation
- Combinatorial Bernoulli factories
- On the complexity of computing maximum entropy for Markovian models
- scientific article; zbMATH DE number 1241791 (Why is no real title available?)
- Random walks in polytopes and negative dependence
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- On geodesically convex formulations for the Brascamp-Lieb constant
- On the computability of continuous maximum entropy distributions with applications
- Generalized maximum entropy estimation
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Maximum entropy and integer partitions
- Efficiently list‐edge coloring multigraphs asymptotically optimally
- Maximum Entropy Distributions with Applications to Graph Simulation
- Complexity of robust orbit problems for torus actions and the abc-conjecture
- Minimizing the determinant of the graph Laplacian
- Optimization, complexity and invariant theory (invited talk)
- Nonlinear dynamics for the Ising model
- Computing the maximum-entropy extension of given discrete probability distributions
- Computational implications of reducing data to sufficient statistics
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- Random weighting, asymptotic counting, and inverse isoperimetry
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)
