The following pages link to Ran Raz (Q168589):
Displaying 50 items.
- Bounds on 2-query locally testable codes with affine tests (Q280942) (← links)
- Regular resolution lower bounds for the weak pigeonhole principle (Q558246) (← links)
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors (Q619913) (← links)
- Lower bounds and separations for constant depth multilinear circuits (Q626617) (← links)
- Sub-constant error probabilistically checkable proof of almost-linear size (Q626681) (← links)
- PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
- A lower bound for adaptively-secure collective coin flipping protocols (Q822636) (← links)
- Quantum information and the PCP theorem (Q835644) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- The strength of multilinear proofs (Q1024659) (← links)
- (Q1380788) (redirect page) (← links)
- Lower bounds on the distortion of embedding finite metric spaces in graphs (Q1380790) (← links)
- Deterministic polynomial identity testing in non-commutative models (Q1781113) (← links)
- Approximating CVP to within almost-polynomial factors is NP-hard (Q1878613) (← links)
- On the ``log rank''-conjecture in communication complexity (Q1906853) (← links)
- Super-logarithmic depth lower bounds via the direct sum in communication complexity (Q1918946) (← links)
- Fourier analysis for probabilistic communication complexity (Q1918947) (← links)
- Arthur-Merlin games in Boolean decision trees (Q1961380) (← links)
- Separation of the monotone NC hierarchy (Q1977414) (← links)
- Quantum versus randomized communication complexity, with efficient players (Q2099674) (← links)
- Balancing syntactically multilinear arithmetic circuits (Q2269004) (← links)
- Arthur-Merlin streaming complexity (Q2347803) (← links)
- Deterministic extractors for affine sources over large fields (Q2390150) (← links)
- A time lower bound for satisfiability (Q2581273) (← links)
- Distance labeling in graphs (extended abstract) (Q2768294) (← links)
- On the space complexity of linear programming with preprocessing (Q2800577) (← links)
- PCP characterizations of NP: towards a polynomially-small error-probability (Q2819531) (← links)
- On recycling the randomness of states in space bounded computation (Q2819543) (← links)
- Exponential separation of quantum and classical communication complexity (Q2819566) (← links)
- Bounds on locally testable codes with unique tests (Q2826056) (← links)
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner (Q2843256) (← links)
- Efficient Multiparty Protocols via Log-Depth Threshold Formulae (Q2849395) (← links)
- Tensor-rank and lower bounds for arithmetic formulas (Q2875193) (← links)
- Sub-constant error low degree test of almost-linear size (Q2931366) (← links)
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound (Q2963581) (← links)
- Two Sides of the Coin Problem (Q2969650) (← links)
- (Q2969656) (← links)
- Competing provers protocols for circuit evaluation (Q2986894) (← links)
- (Q3002768) (← links)
- (Q3002820) (← links)
- The Surprise Examination Paradox and the Second Incompleteness Theorem (Q3010559) (← links)
- A Counterexample to Strong Parallel Repetition (Q3093622) (← links)
- Probabilistically Checkable Arguments (Q3183562) (← links)
- Pseudorandom Generators for Regular Branching Programs (Q3190691) (← links)
- (Q3191608) (← links)
- Higher lower bounds on monotone size (Q3192005) (← links)
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits (Q3395047) (← links)
- Analyzing linear mergers (Q3503607) (← links)
- Interactive PCP (Q3519531) (← links)
- Resolution lower bounds for the weak pigeonhole principle (Q3579188) (← links)
