Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
From MaRDI portal
Publication:1201152
DOI10.1016/0022-0000(92)90047-MzbMATH Open0769.68040MaRDI QIDQ1201152FDOQ1201152
Authors: Noam Nisan, László Babai, Mario Szegedy 
Publication date: 17 January 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Recommendations
lower boundspseudorandom sequencesBoolean formulasbranching programspolynomial time computable functionsmultiparty-communication complexitypseudorandom generator for Logspace
Cites Work
- Title not available (Why is that?)
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Pseudorandom bits for constant depth circuits
- The BNS lower bound for multi-party protocols is nearly optimal
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Title not available (Why is that?)
- On read-once vs. multiple access to randomness in logspace
- On the cover time of random walks on graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Efficient Parallel Pseudorandom Number Generation
- A time-space tradeoff for language recognition
- Two time-space tradeoffs for element distinctness
Cited In (68)
- Lifting query complexity to time-space complexity for two-way finite automata
- Paradigms for Unconditional Pseudorandom Generators
- Simple optimal hitting sets for small-success RL
- Harmonic analysis, real approximation, and the communication complexity of Boolean functions
- Monomial Boolean functions with large high-order nonlinearities
- The splitting power of branching programs of bounded repetition and CNFs of bounded width
- Time-Space Complexity Advantages for Quantum Computing
- Simultaneous multiparty communication protocols for composed functions
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- The hardest halfspace
- Pseudorandom generators for combinatorial checkerboards
- Block-symmetric polynomials correlate with parity better than symmetric
- One-way multiparty communication lower bound for pointer jumping with applications
- On the power of circuits with gates of low \(L_{1}\) norms.
- On the number of zero-patterns of a sequence of polynomials
- Title not available (Why is that?)
- Construction of Very Hard Functions for Multiparty Communication Complexity
- Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Space pseudorandom generators by communication complexity lower bounds
- Random low-degree polynomials are hard to approximate
- 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
- On the non-deterministic communication complexity of regular languages
- The correlation between parity and quadratic polynomials mod \(3\)
- Limits of Boolean functions on \(\mathbb{F}_p^n\)
- Leakage-resilient key exchange and two-seed extractors
- Tradeoff lower lounds for stack machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the communication complexity of high-dimensional permutations
- Modular statistics for subgraph counts in sparse random graphs
- On the Non-deterministic Communication Complexity of Regular Languages
- Pseudorandom functions: three decades later
- The mother of all leakages: how to simulate noisy leakages via bounded leakage (almost) for free
- Graph exploration by a finite automaton
- Synthesizers and their application to the parallel construction of pseudo-random functions
- 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
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Communication vs. computation
- Time space tradeoffs for attacks against one-way functions and PRGs
- Efficient oblivious branching programs for threshold and mod functions
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Hadamard tensors and lower bounds on multiparty communication complexity
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Quantum multiparty communication complexity and circuit lower bounds
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- Typically-correct derandomization for small time and space
- The multiparty communication complexity of set disjointness
- Communication complexity of some number theoretic functions
- The communication complexity of addition
- Time-space tradeoffs for satisfiability
- Impact of memory size on graph exploration capability
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Communication lower bounds via critical block sensitivity
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
- Separation of unbounded-error models in multi-party communication complexity
- On multiparty communication with large versus unbounded error
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)
