Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)
From MaRDI portal
Publication:2988848
DOI10.1007/978-3-319-55911-7_38zbMath1485.68099OpenAlexW2557472829MaRDI QIDQ2988848
Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Publication date: 19 May 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_38
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Boolean functions (06E30) Communication complexity, information complexity (68Q11)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smallest compact formulation for the permutahedron
- Finding biclusters by random projections
- Expressing combinatorial optimization problems by linear programs
- Communication complexity and combinatorial lattice theory
- A comparison of two lower-bound methods for communication complexity
- Some new bounds for cover-free families through biclique covers
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On Bipartite and Multipartite Clique Problems
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Average Case Polyhedral Complexity of the Maximum Stable Set Problem
- Independent Sets in Random Graphs from the Weighted Second Moment Method
- Communication Complexity (for Algorithm Designers)
- Communication Complexity
- Strong Isometric Dimension, Biclique Coverings, and Sperner's Theorem
- Combinatorial Pattern Matching
- Secure Frameproof Code Through Biclique Cover
- Linear vs. semidefinite extended formulations
- Probability and Computing
- Superboolean rank and the size of the largest triangular submatrix of a random matrix
This page was built for publication: Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)
