Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
From MaRDI portal
Publication:1201152
DOI10.1016/0022-0000(92)90047-MzbMath0769.68040MaRDI QIDQ1201152
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)
lower boundsbranching programspseudorandom sequencesBoolean formulaspolynomial time computable functionsmultiparty-communication complexitypseudorandom generator for Logspace
Related Items
On relations between counting communication complexity classes, The correlation between parity and quadratic polynomials mod \(3\), Hellinger volume and number-on-the-forehead communication complexity, Communication Complexity and Lower Bounds on Multilective Computations, Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance, Time-Space Complexity Advantages for Quantum Computing, Communication Lower Bounds via Critical Block Sensitivity, Hadamard tensors and lower bounds on multiparty communication complexity, Block-symmetric polynomials correlate with parity better than symmetric, Efficient oblivious branching programs for threshold and mod functions, On the power of circuits with gates of low \(L_{1}\) norms., Pseudorandom generators for combinatorial checkerboards, Lifting query complexity to time-space complexity for two-way finite automata, Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, Unnamed Item, Monomial Boolean functions with large high-order nonlinearities, Simple Optimal Hitting Sets for Small-Success RL, Random low-degree polynomials are hard to approximate, Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs, On the Non-deterministic Communication Complexity of Regular Languages, Limits of Boolean functions on \(\mathbb{F}_p^n\), On the number of zero-patterns of a sequence of polynomials, Unexpected upper bounds on the complexity of some communication games, Interleaved Group Products, Improved Extractors for Recognizable and Algebraic Sources, The NOF multiparty communication complexity of composed functions, The hardest halfspace, Impact of memory size on graph exploration capability, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, Communication complexity of some number theoretic functions, The communication complexity of addition, Harmonic analysis, real approximation, and the communication complexity of Boolean functions, One-way multiparty communication lower bound for pointer jumping with applications, Modular statistics for subgraph counts in sparse random graphs, ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES, Unnamed Item, Unnamed Item, Quantum multiparty communication complexity and circuit lower bounds, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Tradeoff lower lounds for stack machines, The Multiparty Communication Complexity of Set Disjointness, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, The mother of all leakages: how to simulate noisy leakages via bounded leakage (almost) for free, Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Typically-correct derandomization for small time and space, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, Time-space tradeoffs for satisfiability, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Unnamed Item, Unnamed Item, Synthesizers and their application to the parallel construction of pseudo-random functions, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Communication Lower Bounds Using Directional Derivatives, On the complexity of planar Boolean circuits, Construction of Very Hard Functions for Multiparty Communication Complexity, Graph exploration by a finite automaton, Leakage-resilient key exchange and two-seed extractors, Pseudorandom Functions: Three Decades Later, Time-space tradeoffs for branching programs, Hypergraphs, quasi-randomness, and conditions for regularity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom bits for constant depth circuits
- Two time-space tradeoffs for element distinctness
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- On read-once vs. multiple access to randomness in logspace
- The BNS lower bound for multi-party protocols is nearly optimal
- On the cover time of random walks on graphs
- A time-space tradeoff for language recognition
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Efficient Parallel Pseudorandom Number Generation
