Stem derandom$ (all stems)

17 papers:

STOC-2014-GoldreichW #algorithm #on the

On derandomizing algorithms that err extremely rarely (OG, AW), pp. 109–118.

STOC-2013-Williams #proving

Natural proofs versus derandomization (RW), pp. 21–30.

STOC-2011-MoserS #algorithm #satisfiability

A full derandomization of schöning’s k-SAT algorithm (RAM, DS), pp. 245–252.

ICALP-v2-2009-CooperIKK #graph #random #using

Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies (CC, DI, RK, AK), pp. 411–422.

STOC-2008-ImpagliazzoJKW #theorem

Uniform direct product theorems: simplified, optimized, and derandomized (RI, RJ, VK, AW), pp. 579–588.

STOC-2006-Impagliazzo #algorithm #question #random

Can every randomized algorithm be derandomized? (RI), pp. 373–374.

STOC-2005-AggarwalFGHIS

Derandomization of auctions (GA, AF, AVG, JDH, NI, MS), pp. 619–625.

SAT-J-2004-DantsinW05 #algorithm #satisfiability

Derandomization of Schuler’s Algorithm for SAT (ED, AW), pp. 80–88.

SAT-2005-Rolf #satisfiability

Derandomization of PPSZ for Unique- k-SAT (DR), pp. 216–225.

STOC-2004-ShpilkaW #morphism #testing

Derandomizing homomorphism testing in general groups (AS, AW), pp. 427–435.

SAT-2004-DantsinW #algorithm #satisfiability

Derandomization of Schuler’s Algorithm for SAT (ED, AW), pp. 69–75.

STOC-2003-KabanetsI #bound #polynomial #proving #testing

Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.

STOC-2002-Sivakumar #algorithm #complexity

Algorithmic derandomization via complexity theory (DS), pp. 619–626.

STOC-1998-LewinV #polynomial #question #towards

Checking Polynomial Identities over any Field: Towards a Derandomization? (DL, SPV), pp. 438–447.

STOC-1997-ImpagliazzoW #exponential

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma (RI, AW), pp. 220–229.

ICALP-1997-AndreevCR #trade-off #worst-case

Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs (AEA, AEFC, JDPR), pp. 177–187.

ICALP-1996-AndreevCR #set

Hitting Sets Derandomize BPP (AEA, AEFC, JDPR), pp. 357–368.