Search results for "derandomization"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
20	Oded Goldreich 0001, Salil P. Vadhan, Avi Wigderson	Simplified Derandomization of BPP Using a Hitting Set Generator.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
20	Daniil Musatov	Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization.	CSR	2011	DBLP DOI BibTeX RDF
20	Robin A. Moser, Dominik Scheder	A full derandomization of schöning's k-SAT algorithm.	STOC	2011	DBLP DOI BibTeX RDF
20	Zohar S. Karnin	derandomization of algebraic and geometric problems in theoretical computer science.		2011	RDF
20	Scott Aaronson, Dieter van Melkebeek	A note on circuit lower bounds from derandomization.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
20	Eric Allender, Vikraman Arvind, Fengming Wang	Uniform Derandomization from Pathetic Lower Bounds.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
20	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
20	Robin A. Moser, Dominik Scheder	A Full Derandomization of Schoening's k-SAT Algorithm	CoRR	2010	DBLP BibTeX RDF
20	Mahdi Cheraghchi	Derandomization and Group Testing	CoRR	2010	DBLP BibTeX RDF
20	Daniil Musatov	Theorems about space-bounded Kolmogorov complexity obtained by "naive" derandomization	CoRR	2010	DBLP BibTeX RDF
20	Ronen Shaltiel	Typically-correct derandomization.	SIGACT News	2010	DBLP DOI BibTeX RDF
20	Mahdi Cheraghchi	Derandomization and group testing.	Allerton	2010	DBLP DOI BibTeX RDF
20	Eric Allender, Vikraman Arvind, Fengming Wang	Uniform Derandomization from Pathetic Lower Bounds.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
20	Mahdi Cheraghchi	Applications of Derandomization Theory in Coding.		2010	DOI RDF
20	Russell Impagliazzo, Philippe Moser	A zero-one law for RP and derandomization of AM if NP is not small.	Inf. Comput.	2009	DBLP DOI BibTeX RDF
20	Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz	A New Derandomization of Auctions.	SAGT	2009	DBLP DOI BibTeX RDF
20	Ronen Shaltiel	Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.	CCC	2009	DBLP DOI BibTeX RDF
20	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
20	David P. Williamson, Anke van Zuylen	A simpler and better derandomization of an approximation algorithm for single source rent-or-buy.	Oper. Res. Lett.	2007	DBLP DOI BibTeX RDF
20	Boaz Barak, Shien Jin Ong, Salil P. Vadhan	Derandomization in Cryptography.	SIAM J. Comput.	2007	DBLP DOI BibTeX RDF
20	Qi Cheng 0001	Derandomization of Sparse Cyclotomic Integer Zero Testing.	FOCS	2007	DBLP DOI BibTeX RDF
20	Ilia Binder, Mark Braverman	Derandomization of Euclidean Random Walks.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
20	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
20	Dan Gutfreund, Amnon Ta-Shma	New connections between derandomization, worst-case complexity and average-case complexity.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
20	James M. Kay, Jeff Frolik	Derandomization of Wireless Channel Access using Automata in Sensor Networks.	ICAS	2006	DBLP DOI BibTeX RDF
20	Boaz Barak, Shien Jin Ong, Salil P. Vadhan	Derandomization in Cryptography	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
20	Daniel Rolf	Derandomization of PPSZ for Unique-k-SAT	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
20	Michael Luby, Avi Wigderson	Pairwise Independence and Derandomization.	Found. Trends Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
20	Boaz Barak, Shien Jin Ong, Salil P. Vadhan	Derandomization in Cryptography.	IACR Cryptol. ePrint Arch.	2005	DBLP BibTeX RDF
20	Daniel Rolf	Derandomization of PPSZ for Unique- k-SAT.	SAT	2005	DBLP DOI BibTeX RDF
20	Dan Gutfreund	Derandomization, hard functions, and average-case complexity (דה-רנדומיזציה, פונקציות קשות וסיבוכיות ממוצעת.).		2005	RDF
20	Otfried Cheong, Ketan Mulmuley, Edgar Ramos	Randomization and derandomization.	Handbook of Discrete and Computational Geometry, 2nd Ed.	2004	DBLP DOI BibTeX RDF
20	Evgeny Dantsin, Alexander Wolpert	Derandomization of Schuler's Algorithm for SAT	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
20	Emil Jerábek	Dual weak pigeonhole principle, Boolean complexity, and derandomization.	Ann. Pure Appl. Log.	2004	DBLP DOI BibTeX RDF
20	Evgeny Dantsin, Alexander Wolpert	Derandomization of Schuler's Algorithm for SAT.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF
20	Evgeny Dantsin, Alexander Wolpert	Derandomization of Schuler's Algorithm for SAT.	SAT	2004	DBLP BibTeX RDF
20	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	FSTTCS	2004	DBLP DOI BibTeX RDF
20	Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher	A derandomization using min-wise independent permutations.	J. Discrete Algorithms	2003	DBLP DOI BibTeX RDF
20	Russell Impagliazzo	Hardness as randomness: a survey of universal derandomization	CoRR	2003	DBLP BibTeX RDF
20	Boaz Barak, Shien Jin Ong, Salil P. Vadhan	Derandomization in Cryptography.	CRYPTO	2003	DBLP DOI BibTeX RDF
20	Rahul Santhanam	Resource Tradeoffs and Derandomization	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
20	Valentine Kabanets	Derandomization: A Brief Overview	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
20	Oded Goldreich 0001, Avi Wigderson	Derandomization that is rarely wrong from short advice that is typically good	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
20	Valentine Kabanets	Derandomization: a brief overview.	Bull. EATCS	2002	DBLP BibTeX RDF
20	Oded Goldreich 0001, Avi Wigderson	Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.	RANDOM	2002	DBLP DOI BibTeX RDF
20	Russell Impagliazzo, Avi Wigderson	Randomness vs Time: Derandomization under a Uniform Assumption.	J. Comput. Syst. Sci.	2001	DBLP DOI BibTeX RDF
20	Oded Goldreich 0001, Salil P. Vadhan, Avi Wigderson	Simplified derandomization of BPP using a hitting set generator.	Electron. Colloquium Comput. Complex.	2000	DBLP BibTeX RDF
20	Jirí Matousek 0001	Derandomization in Computational Geometry.	Handbook of Computational Geometry	2000	DBLP DOI BibTeX RDF
20	Edyta Szymanska	Derandomization of a Parallel MIS Algorithm in a Linear Hypergraph.	ICALP Satellite Workshops	2000	DBLP BibTeX RDF
20	Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim	Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-offs.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
20	Hervé Brönnimann, Bernard Chazelle, Jirí Matousek 0001	Product Range Spaces, Sensitive Sampling, and Derandomization.	SIAM J. Comput.	1999	DBLP DOI BibTeX RDF
20	Oded Goldreich 0001, Avi Wigderson	Improved Derandomization of BPP Using a Hitting Set Generator.	RANDOM-APPROX	1999	DBLP DOI BibTeX RDF
20	Dimitris Fotakis 0001, Paul G. Spirakis	Random Walks, Conditional Hitting Sets and Partial Derandomization	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
20	Harry Buhrman, Ronald de Wolf	Lower Bounds for Quantum Search and Derandomization	CoRR	1998	DBLP BibTeX RDF
20	Daniel Lewin 0001, Salil P. Vadhan	Checking Polynomial Identities over any Field: Towards a Derandomization?	STOC	1998	DBLP DOI BibTeX RDF
20	Ralf Salomon	Improving the Preformance of Genetic Algorithms through Derandomization.	Softw. Concepts Tools	1997	DBLP BibTeX RDF
20	Michael T. Goodrich, Edgar A. Ramos	Bounded-Independence Derandomization of Geometric Partitioning with Applications to Parallel Fixed-Dimensional Linear Programming.	Discret. Comput. Geom.	1997	DBLP DOI BibTeX RDF
20	Xiaotie Deng, Sanjeev Mahajan	The Cost of Derandomization: Computability or Competitiveness.	SIAM J. Comput.	1997	DBLP DOI BibTeX RDF
20	Detlef Sieling	Derandomization.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
20	Noga Alon, Moni Naor	Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.	Algorithmica	1996	DBLP DOI BibTeX RDF
20	Jirí Matousek 0001	Derandomization in Computational Geometry.	J. Algorithms	1996	DBLP DOI BibTeX RDF
20	Yijie Han	A Fast Derandomization Scheme and Its Applications.	SIAM J. Comput.	1996	DBLP DOI BibTeX RDF
20	Noga Alon	Derandomization Via Small Sample Spaces (Abstract).	SWAT	1996	DBLP DOI BibTeX RDF
20	Michael E. Saks	Randomization and Derandomization in Space_Bounded Computation.	CCC	1996	DBLP DOI BibTeX RDF	pseudorandom generators, Probabilistic computation, space-bounded computation
20	Thomas Hofmeister, Hanno Lefmann	Derandomization for Sparse Approximations and Independent Sets.	MFCS	1995	DBLP DOI BibTeX RDF
20	Joel Spencer	Randomization, Derandomization and Antirandomization: Three Games.	Theor. Comput. Sci.	1994	DBLP DOI BibTeX RDF
20	Yijie Han	A Fast Derandomization Schemes and Its Applications.	WADS	1991	DBLP DOI BibTeX RDF
20	Yijie Han, Yoshihide Igarashi	Derandomization by Exploiting Redundancy and Mutual Independence.	SIGAL International Symposium on Algorithms	1990	DBLP DOI BibTeX RDF
20	Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis	Fast Parallel Approximations of hte Maximum Weighted Cut Problem through Derandomization.	FSTTCS	1989	DBLP DOI BibTeX RDF
19	Ronen Shaltiel	Derandomized Parallel Repetition Theorems for Free Games.	CCC	2010	DBLP DOI BibTeX RDF	Derandomization, Randomness extractors, Parallel repetition
19	Dan Gutfreund, Akinori Kawachi	Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.	CCC	2010	DBLP DOI BibTeX RDF	Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting
19	Matt DeVos, Ariel Gabizon	Simple Affine Extractors Using Dimension Expansion.	CCC	2010	DBLP DOI BibTeX RDF	affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness
19	Harry Buhrman, Lance Fortnow, Michal Koucký 0001, Bruno Loff	Derandomizing from Random Strings.	CCC	2010	DBLP DOI BibTeX RDF	Truth-table Reducibility, Kolmogorov Complexity, Derandomization
19	Zeev Dvir, Ariel Gabizon, Avi Wigderson	Extractors And Rank Extractors For Polynomial Sources.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Derandomization, Extractors
19	Christopher Umans	Reconstructive Dispersers and Hitting Set Generators.	Algorithmica	2009	DBLP DOI BibTeX RDF	Hitting set generator, Derandomization, Disperser
19	Jianer Chen, Songjian Lu	Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach.	Algorithmica	2009	DBLP DOI BibTeX RDF	Set splitting, Parametrized algorithm, Randomized algorithm, Derandomization
19	Neeraj Kayal, Shubhangi Saraf	Blackbox Polynomial Identity Testing for Depth 3 Circuits.	FOCS	2009	DBLP DOI BibTeX RDF	Sylvester, Derandomization, Arithmetic circuits
19	Robin A. Moser	A constructive proof of the Lovász local lemma.	STOC	2009	DBLP DOI BibTeX RDF	bounded occurrence sat instances, hypergraph colouring, derandomization, Lovasz local lemma
19	Noga Alon, Shai Gutner	Balanced Hashing, Color Coding and Approximate Counting.	IWPEC	2009	DBLP DOI BibTeX RDF	Approximate counting of subgraphs, derandomization, expanders, perfect hashing, color-coding, k-wise independence
19	Omer Reingold	Undirected connectivity in log-space.	J. ACM	2008	DBLP DOI BibTeX RDF	bounded space algorithms, Derandomization, pseudorandom generator
19	Dan Gutfreund, Salil P. Vadhan	Limitations of Hardness vs. Randomness under Uniform Reductions.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	derandomization, pseudorandom generators, black-box reductions
19	Parikshit Gopalan, Venkatesan Guruswami	Hardness Amplification within NP against Deterministic Algorithms.	CCC	2008	DBLP DOI BibTeX RDF	Hardness Amplication, Error-Correcting Codes, Derandomization, NP
19	Zhi-Zhong Chen, Takayuki Nagoya	Improved approximation algorithms for metric MaxTSP.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Max TSP, Metric Max TSP, Approximation Algorithms, Randomized Algorithms, TSP, Derandomization
19	Anke van Zuylen, David P. Williamson	Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems.	WAOA	2007	DBLP DOI BibTeX RDF	feedback arc set in tournaments, derandomization, rank aggregation
19	Ronen Shaltiel, Christopher Umans	Low-end uniform hardness vs. randomness tradeoffs for AM.	STOC	2007	DBLP DOI BibTeX RDF	hardness vs. randomness tradeoff, hitting-set generator, derandomization, Arthur-Merlin games
19	Noga Alon, Dana Moshkovitz, Shmuel Safra	Algorithmic construction of sets for k-restrictions.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	k-restriction, almost k-wise independence, generalized hashing, splitter, Set-Cover, Derandomization, group testing
19	Oded Goldreich 0001, Madhu Sudan 0001	Locally testable codes and PCPs of almost-linear length.	J. ACM	2006	DBLP DOI BibTeX RDF	error-correcting codes, derandomization, probabilistically checkable proofs, Proof verification
19	Haizhi Xu, Steve J. Chapin	Improving address space randomization with a dynamic offset randomization technique.	SAC	2006	DBLP DOI BibTeX RDF	address space randomization, code islands, derandomization attacks, intrusion mitigation, randomization, denial-of-service attacks
19	Bella Dubrov, Yuval Ishai	On the randomness complexity of efficient sampling.	STOC	2006	DBLP DOI BibTeX RDF	information theoretic cryptography, randomness complexity, compression, derandomization, pseudorandom generators, secure computation
19	Omer Reingold, Luca Trevisan, Salil P. Vadhan	Pseudorandom walks on regular digraphs and the RL vs. L problem.	STOC	2006	DBLP DOI BibTeX RDF	universal traversal sequence, zig-zag product, derandomization, expander graphs, mixing time, space-bounded computation
19	Andrej Bogdanov	Pseudorandom generators for low degree polynomials.	STOC	2005	DBLP DOI BibTeX RDF	derandomization, pseudorandomness
19	Art B. Owen	Variance with alternative scramblings of digital nets.	ACM Trans. Model. Comput. Simul.	2003	DBLP DOI BibTeX RDF	randomization, Derandomization, quasi-Monte Carlo
19	Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor	The online set cover problem.	STOC	2003	DBLP DOI BibTeX RDF	competitive analysis, on-line algorithms, set-cover, derandomization, randomized rounding
19	Peter Sanders 0001, Sebastian Egner, Ludo M. G. M. Tolhuizen	Polynomial time algorithms for network information flow.	SPAA	2003	DBLP DOI BibTeX RDF	communication, multicasting, randomized algorithm, finite field, coding, linear algebra, derandomization, network information theory
19	Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou	An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs.	J. ACM	2000	DBLP DOI BibTeX RDF	short pseudorandom walks on graphs, undirected graph connectivity, computational complexity, derandomization, space bounded computations
19	Michael E. Saks, Aravind Srinivasan, Shiyu Zhou	Explicit OR-Dispersers with Polylogarithmic Degree.	J. ACM	1998	DBLP DOI BibTeX RDF	hashing lemmas, imperfect sources of randomness, measures of information, hardness of approximation, derandomization, expander graphs, time-space tradeoffs, pseudo-random generators, explicit constructions, randomized computation
19	Peter Auer, Philip M. Long, Aravind Srinivasan	Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets.	STOC	1997	DBLP DOI BibTeX RDF	approximations of distributions, machine learning, random graphs, derandomization, pseudorandomness, PAC learning, multiple-instance learning, rectangles, sample complexity, explicit constructions, Ramsey graphs
19	Noam Nisan	Extracting Randomness: How and Why A survey.	CCC	1996	DBLP DOI BibTeX RDF	Randmoness, Computational Complexity, Derandomization, Expanders
14	Anne Auger, Dimo Brockhoff, Nikolaus Hansen	Mirrored variants of the (1, 2)-CMA-ES compared on the noiseless BBOB-2010 testbed.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	benchmarking, black-box optimization
14	Anne Auger, Dimo Brockhoff, Nikolaus Hansen	Mirrored variants of the (1, 4)-CMA-ES compared on the noiseless BBOB-2010 testbed.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	benchmarking, black-box optimization