Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
From MaRDI portal
(Redirected from Publication:1201152)
Recommendations
Cites work
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 2168577 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- A time-space tradeoff for language recognition
- Efficient Parallel Pseudorandom Number Generation
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- On read-once vs. multiple access to randomness in logspace
- On the cover time of random walks on graphs
- Pseudorandom bits for constant depth circuits
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- The BNS lower bound for multi-party protocols is nearly optimal
- Two time-space tradeoffs for element distinctness
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
Cited in
(68)- Separation of unbounded-error models in multi-party communication complexity
- On multiparty communication with large versus unbounded error
- The hardest halfspace
- Pseudorandom generators for combinatorial checkerboards
- One-way multiparty communication lower bound for pointer jumping with applications
- On the power of circuits with gates of low \(L_{1}\) norms.
- Block-symmetric polynomials correlate with parity better than symmetric
- Lifting query complexity to time-space complexity for two-way finite automata
- On the number of zero-patterns of a sequence of polynomials
- Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
- Construction of Very Hard Functions for Multiparty Communication Complexity
- scientific article; zbMATH DE number 7758323 (Why is no real title available?)
- Paradigms for Unconditional Pseudorandom Generators
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Random low-degree polynomials are hard to approximate
- Space pseudorandom generators by communication complexity lower bounds
- Hellinger volume and number-on-the-forehead communication complexity
- Improved Extractors for Recognizable and Algebraic Sources
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
- Communication Complexity and Lower Bounds on Multilective Computations
- Interleaved Group Products
- Simple optimal hitting sets for small-success RL
- Limits of Boolean functions on \(\mathbb{F}_p^n\)
- The correlation between parity and quadratic polynomials mod \(3\)
- On the non-deterministic communication complexity of regular languages
- Tradeoff lower lounds for stack machines
- Leakage-resilient key exchange and two-seed extractors
- Modular statistics for subgraph counts in sparse random graphs
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- On the communication complexity of high-dimensional permutations
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- On the Non-deterministic Communication Complexity of Regular Languages
- Harmonic analysis, real approximation, and the communication complexity of Boolean functions
- Pseudorandom functions: three decades later
- The mother of all leakages: how to simulate noisy leakages via bounded leakage (almost) for free
- Monomial Boolean functions with large high-order nonlinearities
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Graph exploration by a finite automaton
- The splitting power of branching programs of bounded repetition and CNFs of bounded width
- On relations between counting communication complexity classes
- Unexpected upper bounds on the complexity of some communication games
- Communication lower bounds using directional derivatives
- On the complexity of planar Boolean circuits
- The NOF multiparty communication complexity of composed functions
- Hypergraphs, quasi-randomness, and conditions for regularity
- Time-space tradeoffs for branching programs
- Efficient oblivious branching programs for threshold and mod functions
- Communication vs. computation
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Time-Space Complexity Advantages for Quantum Computing
- Hadamard tensors and lower bounds on multiparty communication complexity
- Time space tradeoffs for attacks against one-way functions and PRGs
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Simultaneous multiparty communication protocols for composed functions
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Quantum multiparty communication complexity and circuit lower bounds
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- The communication complexity of addition
- Typically-correct derandomization for small time and space
- The multiparty communication complexity of set disjointness
- Communication complexity of some number theoretic functions
- Impact of memory size on graph exploration capability
- Time-space tradeoffs for satisfiability
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
- Communication lower bounds via critical block sensitivity
This page was built for publication: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201152)
