The following pages link to Russell Impagliazzo (Q202088):
Displaying 50 items.
- Toward a model for backtracking and dynamic programming (Q430838) (← links)
- A stronger model of dynamic programming algorithms (Q547305) (← links)
- Near optimal seperation of tree-like and general resolution (Q558312) (← links)
- Random CNF's are hard for the polynomial calculus (Q626686) (← links)
- The reachability problem for finite cellular automata (Q674292) (← links)
- Exponential lower bounds for the pigeonhole principle (Q687506) (← links)
- Models of greedy algorithms for graph problems (Q834580) (← links)
- Reducing the seed length in the Nisan-Wigderson generator (Q879167) (← links)
- On the complexity of succinct zero-sum games (Q1024660) (← links)
- Chernoff-type direct product theorems (Q1027975) (← links)
- The relative complexity of NP search problems (Q1273858) (← links)
- Improved depth lower bounds for small distance connectivity (Q1293359) (← links)
- A tight relationship between generic oracles and type-2 complexity theory (Q1369098) (← links)
- (Q1377577) (redirect page) (← links)
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← links)
- Homogenization and the polynomial calculus (Q1430569) (← links)
- Communication complexity towards lower bounds on circuit depth (Q1601024) (← links)
- Which problems have strongly exponential complexity? (Q1604206) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Limits on the power of parallel random access machines with weak forms of write conflict resolution (Q1816745) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} (Q1949746) (← links)
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm (Q1961057) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- The fine-grained complexity of multi-dimensional ordering properties (Q2093566) (← links)
- On dice and coins: Models of computation for random generation (Q2366558) (← links)
- A zero-one law for RP and derandomization of AM if NP is not small (Q2389331) (← links)
- The resolution complexity of independent sets and vertex covers in random graphs (Q2474203) (← links)
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs (Q2475410) (← links)
- Logics for reasoning about cryptographic constructions (Q2490263) (← links)
- Efficient cryptographic schemes provably as secure as subset sum (Q2563542) (← links)
- (Q2754208) (← links)
- (Q2768397) (← links)
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility (Q2800573) (← links)
- Pseudorandomness for network algorithms (Q2817628) (← links)
- Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space (Q2817796) (← links)
- Security-preserving hardness-amplification for any regular one-way function (Q2819544) (← links)
- Finding Heavy Hitters from Lossy or Noisy Data (Q2851870) (← links)
- Designated Verifier Proofs and Their Applications (Q2876894) (← links)
- Can every randomized algorithm be derandomized? (Q2931400) (← links)
- Formula Caching in DPLL (Q2947546) (← links)
- On the Exact Complexity of Evaluating Quantified k-CNF (Q3058691) (← links)
- Simultaneous Secrecy and Reliability Amplification for a General Channel Model (Q3179359) (← links)
- Extractors and pseudo-random generators with optimal seed length (Q3191965) (← links)
- Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification (Q3558014) (← links)
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized (Q3586194) (← links)
- Constructive Proofs of Concentration Bounds (Q3588439) (← links)
- Online Algorithms to Minimize Resource Reallocations and Network Communication (Q3595375) (← links)
- Security Amplification for Interactive Cryptographic Primitives (Q3611763) (← links)
- Chernoff-Type Direct Product Theorems (Q3612567) (← links)
