scientific article; zbMATH DE number 524134
From MaRDI portal
Publication:4284623
Recommendations
Cited in
(54)- On data structures and asymmetric communication complexity
- On the power of circuits with gates of low \(L_{1}\) norms.
- A distributed algorithm for spectral sparsification of graphs with applications to data clustering
- The unbounded-error communication complexity of symmetric functions
- Lower bounds for predecessor searching in the cell probe model
- Polynomial threshold functions and Boolean threshold circuits
- Upper and lower bounds on the power of advice
- A lower bound for depth-3 circuits with MOD m gates
- Hellinger volume and number-on-the-forehead communication complexity
- New bounds for the garden-hose model
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- One-round multi-party communication complexity of distinguishing sums
- Interpolation by a Game
- Lower bounds on threshold and related circuits via communication complexity
- Randomized feasible interpolation and monotone circuits with a local oracle
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Upper bounds on multiparty communication complexity of shifts
- Separation of unbounded-error models in multi-party communication complexity
- scientific article; zbMATH DE number 773999 (Why is no real title available?)
- The NOF multiparty communication complexity of composed functions
- Stabbing planes
- Approximate degree and the complexity of depth three circuits
- Satisfiability and derandomization for small polynomial threshold circuits
- Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
- Approximate Degree in Classical and Quantum Computing
- Equality alone does not simulate randomness
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Sign rank vs discrepancy
- scientific article; zbMATH DE number 7250146 (Why is no real title available?)
- The communication complexity of addition
- Bounds on Threshold Gate Realizability
- The large-error approximate degree of \(\mathrm{AC}^0\)
- String Matching: Communication, Circuits, and Learning.
- Improved Extractors for Recognizable and Algebraic Sources
- The communication complexity of functions with large outputs
- Communication complexity of discrete fair division
- A note on the power of majority gates and modular gates
- On the computation of Boolean functions by analog circuits of bounded fan-in
- A hierarchy of constant communication complexity
- Pseudo-deterministic query complexity of search problems
- Communication complexity and discrepancy of halfplanes
- Distributional PAC-learning from Nisan's natural proofs
- Randomized communication and implicit graph representations
- On the communication complexity of finding a king in a tournament
- The communication complexity of distributed maximization
- Agnostic membership query learning with nontrivial savings: new results and techniques
- Simple heuristics yield provable algorithms for masked low-rank approximation
- Better boosting of communication oracles, or not
- Secret sharing, slice formulas, and monotone real circuits
- Multiparty communication complexity of collision-finding and cutting planes proofs of concise pigeonhole principles
- Equality is far weaker than constant-cost communication
- Powering requires threshold depth 3
- Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4284623)
