The Matching Polytope has Exponential Extension Complexity (Q4640350): Difference between revisions

Latest revision as of 09:41, 10 July 2024

scientific article; zbMATH DE number 6451554

The matching polytope has exponential extension complexity

Language	Label	Description	Also known as
English	The Matching Polytope has Exponential Extension Complexity	scientific article; zbMATH DE number 6451554	The matching polytope has exponential extension complexity

Statements

instance of

scholarly article

0 references

title

The Matching Polytope has Exponential Extension Complexity (English)

0 references

The matching polytope has exponential extension complexity (English)

0 references

0 references

0 references

Proceedings of the forty-sixth annual ACM symposium on Theory of computing

0 references

publication date

17 May 2018

0 references

26 June 2015

0 references

full work available at URL

https://arxiv.org/abs/1311.2369

0 references

zbMATH Keywords

extension complexity

0 references

linear programming

0 references

matching

0 references

combinatorial optimization

0 references

linear programming relaxations

0 references

polytopes

0 references

MaRDI profile type

MaRDI publication profile

0 references

describes a project that uses

SuLQ

0 references

cites work

Bounds on the Sample Complexity for Private Learning and Private Data Release

0 references

Characterizing the sample complexity of private learners

0 references

Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

0 references

Q5302085

0 references

Collusion-secure fingerprinting for digital data

0 references

Faster private release of marginals on small databases

0 references

Lower Bounds in Differential Privacy

0 references

Our Data, Ourselves: Privacy Via Distributed Noise Generation

0 references

Theory of Cryptography

0 references

Q3549600

0 references

On the complexity of differentially private data release

0 references

Efficient algorithms for privately releasing marginals via convex relaxations

0 references

Advances in Cryptology – CRYPTO 2004

0 references

New Efficient Attacks on Statistical Disclosure Control Mechanisms

0 references

Privately Releasing Conjunctions and the Statistical Query Barrier

0 references

Iterative Constructions and Private Data Release

0 references

On the geometry of differential privacy

0 references

The price of privately releasing contingency tables and the spectra of random matrices with correlated rows

0 references

The Geometry of Differential Privacy: The Small Database and Approximate Cases

0 references

Differential Privacy and the Fat-Shattering Dimension of Linear Queries

0 references

Interactive privacy via the median mechanism

0 references

Faster Algorithms for Privately Releasing Marginals

0 references

Answering n <sub>{2+o(1)}</sub> counting queries with differential privacy is hard

0 references

Identifiers

zbMATH Open document ID

0 references

0 references

0 references

10.1145/2591796.2591834

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4640350

@@ Property / cites work @@
+Bounds on the Sample Complexity for Private Learning and Private Data Release
+Normal rank
@@ Property / cites work @@
+Characterizing the sample complexity of private learners
+Normal rank
@@ Property / cites work @@
+Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
+Normal rank
@@ Property / cites work @@
+Q5302085
@@ Property / cites work: Q5302085 / rank @@
+Normal rank
@@ Property / cites work @@
+Collusion-secure fingerprinting for digital data
@@ Property / cites work: Collusion-secure fingerprinting for digital data / rank @@
+Normal rank
@@ Property / cites work @@
+Faster private release of marginals on small databases
+Normal rank
@@ Property / cites work @@
+Lower Bounds in Differential Privacy
@@ Property / cites work: Lower Bounds in Differential Privacy / rank @@
+Normal rank
@@ Property / cites work @@
+Our Data, Ourselves: Privacy Via Distributed Noise Generation
+Normal rank
@@ Property / cites work @@
+Theory of Cryptography
@@ Property / cites work: Theory of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549600
@@ Property / cites work: Q3549600 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of differentially private data release
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for privately releasing marginals via convex relaxations
+Normal rank
@@ Property / cites work @@
+Advances in Cryptology – CRYPTO 2004
@@ Property / cites work: Advances in Cryptology – CRYPTO 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+New Efficient Attacks on Statistical Disclosure Control Mechanisms
+Normal rank
@@ Property / cites work @@
+Privately Releasing Conjunctions and the Statistical Query Barrier
+Normal rank
@@ Property / cites work @@
+Iterative Constructions and Private Data Release
@@ Property / cites work: Iterative Constructions and Private Data Release / rank @@
+Normal rank
@@ Property / cites work @@
+On the geometry of differential privacy
@@ Property / cites work: On the geometry of differential privacy / rank @@
+Normal rank
@@ Property / cites work @@
+The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
+Normal rank
@@ Property / cites work @@
+The Geometry of Differential Privacy: The Small Database and Approximate Cases
+Normal rank
@@ Property / cites work @@
+Differential Privacy and the Fat-Shattering Dimension of Linear Queries
+Normal rank
@@ Property / cites work @@
+Interactive privacy via the median mechanism
@@ Property / cites work: Interactive privacy via the median mechanism / rank @@
+Normal rank
@@ Property / cites work @@
+Faster Algorithms for Privately Releasing Marginals
+Normal rank
@@ Property / cites work @@
+Answering n             <sub>{2+o(1)}</sub>             counting queries with differential privacy is hard
+Normal rank