Pages that link to "Item:Q1202933"
From MaRDI portal
The following pages link to On the distributional complexity of disjointness (Q1202933):
Displaying 50 items.
- Common information and unique disjointness (Q343843) (← links)
- Zero-information protocols and unambiguity in Arthur-Merlin communication (Q343848) (← links)
- A direct product theorem for two-party bounded-round public-coin communication complexity (Q343852) (← links)
- Certifying equality with limited interaction (Q343864) (← links)
- A discrepancy lower bound for information complexity (Q343867) (← links)
- Average case polyhedral complexity of the maximum stable set problem (Q344955) (← links)
- On a theorem of Razborov (Q445247) (← links)
- An information statistics approach to data stream and communication complexity (Q598248) (← links)
- Exponential separation of quantum and classical online space complexity (Q733715) (← links)
- Extended formulations, nonnegative factorizations, and randomized communication protocols (Q745681) (← links)
- On the extension complexity of combinatorial polytopes (Q745682) (← links)
- Testing computability by width-two OBDDs (Q764366) (← links)
- On probabilistic pushdown automata (Q989292) (← links)
- Sketching information divergences (Q1009269) (← links)
- New bounds on classical and quantum one-way communication complexity (Q1029354) (← links)
- On the P versus NP intersected with co-NP question in communication complexity (Q1044738) (← links)
- Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
- The corruption bound, log-rank, and communication complexity (Q1621501) (← links)
- Memory lower bounds of reductions revisited (Q1648781) (← links)
- The landscape of communication complexity classes (Q1653337) (← links)
- A note on hardness of diameter approximation (Q1705693) (← links)
- Information complexity and applications. (Q1731897) (← links)
- On the power of randomized multicounter machines (Q1763706) (← links)
- Quantum communication and complexity. (Q1853475) (← links)
- On the complexity of data disjunctions. (Q1853503) (← links)
- On rank vs. communication complexity (Q1906852) (← links)
- Fourier analysis for probabilistic communication complexity (Q1918947) (← links)
- Fast distributed approximation for TAP and 2-edge-connectivity (Q1988524) (← links)
- Information-theoretic approximations of the nonnegative rank (Q2012181) (← links)
- Nondeterministic and randomized Boolean hierarchies in communication complexity (Q2041245) (← links)
- Upper bounds on communication in terms of approximate rank (Q2117081) (← links)
- On the streaming indistinguishability of a random permutation and a random function (Q2119020) (← links)
- Sublinear-time distributed algorithms for detecting small cliques and even cycles (Q2146871) (← links)
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond (Q2159471) (← links)
- Explicit exponential lower bounds for exact hyperplane covers (Q2166321) (← links)
- Communication complexity with small advantage (Q2182866) (← links)
- Fooling views: a new lower bound technique for distributed computations under congestion (Q2220402) (← links)
- The complexity of dissociation set problems in graphs (Q2275943) (← links)
- A stable marriage requires communication (Q2278950) (← links)
- Message lower bounds via efficient network synchronization (Q2292919) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- A short proof that the extension complexity of the correlation polytope grows exponentially (Q2340413) (← links)
- The unbounded-error communication complexity of symmetric functions (Q2428632) (← links)
- Finding longest increasing and common subsequences in streaming data (Q2498982) (← links)
- A distributed algorithm for directed minimum-weight spanning tree (Q2689838) (← links)
- Lower bounds for number-in-hand multiparty communication complexity, made easy (Q2796207) (← links)
- Exponential lower bounds for polytopes in combinatorial optimization (Q2796404) (← links)
- New strong direct product results in communication complexity (Q2796407) (← links)
- Superlinear advantage for exact quantum algorithms (Q2805516) (← links)
- Upper and lower bounds on the power of advice (Q2816830) (← links)