Search results for "Derandomization"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Olivier Teytaud, Sylvain Gelly	DCMA: yet another derandomization in covariance-matrix-adaptation.	GECCO	2007	DBLP DOI BibTeX RDF	quasi-random, evolution strategies, derandomization
3	Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan	Derandomization of auctions.	STOC	2005	DBLP DOI BibTeX RDF	auctions, mechanism design, derandomization
3	D. Sivakumar	Algorithmic Derandomization via Complexity Theory. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	Johnson-Lindenstrauss Lemma, Derandomization, randomized rounding
3	Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim	A New General Derandomization Method.	J. ACM	1998	DBLP DOI BibTeX RDF	BPP, derandomization, Boolean circuits
3	Moni Naor, Leonard J. Schulman, Aravind Srinivasan	Splitters and Near-Optimal Derandomization.	FOCS	1995	DBLP DOI BibTeX RDF	splitters, near-optimal derandomization, fairly general method, k-restrictions, probabilistic bound, near-optimal constructions, fixed-subgraph finding algorithms, deterministic constructions, local-coloring protocol, computational complexity, learning, probability, computational linguistics, hardness of approximation, set cover, derandomization, randomised algorithms, exhaustive testing
2	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators and Typically-Correct Derandomization.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
2	Gary L. Miller, Donald Sheehy	Approximate center points with proofs.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	Tverberg's theorem, centerpoints, approximation algorithms, derandomization
2	Marius Zimand	Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time.	Computational Complexity	2008	DBLP DOI BibTeX RDF	Subject classification, 68Q15
2	Moritz Müller	Parameterized Derandomization.	IWPEC	2008	DBLP DOI BibTeX RDF
2	Olivier Teytaud	When Does Quasi-random Work?.	PPSN	2008	DBLP DOI BibTeX RDF	Evolution Strategies, Derandomization
2	H. Venkateswaran	Derandomization of Probabilistic Auxiliary Pushdown Automata Classes.	IEEE Conference on Computational Complexity	2006	DBLP DOI BibTeX RDF
2	Russell Impagliazzo	Can every randomized algorithm be derandomized?	STOC	2006	DBLP DOI BibTeX RDF	algebraic circuit complexity, probabilistic algorithms, derandomization, circuit complexity, complexity classes, pseudo-randomness
2	Harry Buhrman, Lance Fortnow, Aduri Pavan	Some Results on Derandomization.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
2	Ankur Bhargava, S. Rao Kosaraju	Derandomization of Dimensionality Reduction and SDP Based Algorithms.	WADS	2005	DBLP DOI BibTeX RDF
2	Amir Shpilka, Avi Wigderson	Derandomizing homomorphism testing in general groups.	STOC	2004	DBLP DOI BibTeX RDF	homomorphism testing, derandomization, linearity testing
2	Harry Buhrman, Lance Fortnow, Aduri Pavan	Some Results on Derandomization.	STACS	2003	DBLP DOI BibTeX RDF
2	Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy	Derandomization and Distinguishing Complexity.	IEEE Conference on Computational Complexity	2003	DBLP DOI BibTeX RDF
2	Rahul Santhanam, Dieter van Melkebeek	Holographic Proofs and Derandomization.	IEEE Conference on Computational Complexity	2003	DBLP DOI BibTeX RDF
2	Valentine Kabanets, Russell Impagliazzo	Derandomizing polynomial identity tests means proving circuit lower bounds.	STOC	2003	DBLP DOI BibTeX RDF	BPP, NEXP, circuit lower bounds, derandomization, polynomial identity testing
2	D. Sivakumar	Algorithmic derandomization via complexity theory.	STOC	2002	DBLP DOI BibTeX RDF
2	Benjamin Doerr	Antirandomizing the Wrong Game.	ICALP	2002	DBLP DOI BibTeX RDF	Games, randomization, derandomization
2	Adam Klivans	On the Derandomization of Constant Depth Circuits.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
2	Lance Fortnow	Comparing Notions of Full Derandomization. (PDF / PS)	IEEE Conference on Computational Complexity	2001	DBLP DOI BibTeX RDF
2	Eric Allender	When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.	FSTTCS	2001	DBLP DOI BibTeX RDF
2	Chi-Jen Lu	Derandomizing Arthur-Merlin games under uniform assumptions.	Computational Complexity	2001	DBLP DOI BibTeX RDF	graph nonisomorphism problem, nondeterminism, Derandomization, uniformity, Arthur-Merlin games
2	Bernard Chazelle	Irregularities of Distribution, Derandomization, and Complexity Theory.	FSTTCS	2000	DBLP DOI BibTeX RDF
2	Valentine Kabanets	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	probabilistic complexity classes, uniform setting, derandomization
2	Yijie Han, Yoshihide Igarashi	Parallel PROFIT/COST Algorithms Through Fast Derandomization.	Acta Inf.	1999	DBLP DOI BibTeX RDF
2	Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson	Near-Optimal Conversion of Hardness into Pseudo-Randomness.	FOCS	1999	DBLP DOI BibTeX RDF	Pseudo-Ranndom Generators, Derandomization
2	Peter Bro Miltersen, N. V. Vinodchandran	Derandomizing Arthur-Merlin Games Using Hitting Sets.	FOCS	1999	DBLP DOI BibTeX RDF	derandomization, hitting sets, Arthur-Merlin games
2	Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher	A Derandomization Using Min-Wise Independent Permutations.	RANDOM	1998	DBLP DOI BibTeX RDF
2	Roy Armoni	On the Derandomization of Space-Bounded Computations.	RANDOM	1998	DBLP DOI BibTeX RDF
2	Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin	Approximating a Finite Metric by a Small Number of Tree Metrics.	FOCS	1998	DBLP DOI BibTeX RDF	probabilistic approximation of metric spaces, low diameter partitioning, real normed spaces, algorithms, linear programming, approximation, metric space, derandomization, tree metric
2	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.	ICALP	1997	DBLP DOI BibTeX RDF
2	Hervé Brönnimann, Bernard Chazelle, Jirí Matousek	Product Range Spaces, Sensitive Sampling, and Derandomization	FOCS	1993	DBLP DOI BibTeX RDF	3-dimensional space, product range spaces, sensitive sampling, sampling theorems, standard finite VC-dimensional case, optimal deterministic convex hull algorithm, n-point set, deterministic algorithm, derandomization
1	Somit Gupta, Soumojit Sarkar, Arne Storjohann, Johnny Valeriote	Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x].	J. Symb. Comput.	2012	DBLP DOI BibTeX RDF
1	Thomas Müller-Gronbach, Klaus Ritter, Larisa Yaroslavtseva	Derandomization of the Euler scheme for scalar stochastic differential equations.	J. Complexity	2012	DBLP DOI BibTeX RDF
1	Luca Trevisan	Pseudorandomness and derandomization.	ACM Crossroads	2012	DBLP DOI BibTeX RDF
1	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.	Computational Complexity	2012	DBLP DOI BibTeX RDF
1	Linqing Tang	On the derandomization of the graph test for homomorphism over groups.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
1	Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan	Derandomization of auctions.	Games and Economic Behavior	2011	DBLP DOI BibTeX RDF
1	Scott Aaronson, Dieter van Melkebeek	On Circuit Lower Bounds from Derandomization.	Theory of Computing	2011	DBLP DOI BibTeX RDF
1	Ronen Shaltiel	Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.	Computational Complexity	2011	DBLP DOI BibTeX RDF
1	Ankur Sahai	Derandomization of Online Assignment Algorithms for Dynamic Graphs	CoRR	2011	DBLP BibTeX RDF
1	Mahdi Cheraghchi	Applications of Derandomization Theory in Coding	CoRR	2011	DBLP BibTeX RDF
1	Oded Goldreich, Salil P. Vadhan, Avi Wigderson	Simplified Derandomization of BPP Using a Hitting Set Generator.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Daniil Musatov	Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization.	CSR	2011	DBLP DOI BibTeX RDF
1	Robin A. Moser, Dominik Scheder	A full derandomization of schöning's k-SAT algorithm.	STOC	2011	DBLP DOI BibTeX RDF
1	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Scott Aaronson, Dieter van Melkebeek	A note on circuit lower bounds from derandomization.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Eric Allender, Vikraman Arvind, Fengming Wang	Uniform Derandomization from Pathetic Lower Bounds.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Mahdi Cheraghchi	Derandomization and Group Testing	CoRR	2010	DBLP BibTeX RDF
1	Robin A. Moser, Dominik Scheder	A Full Derandomization of Schoening's k-SAT Algorithm	CoRR	2010	DBLP BibTeX RDF
1	Daniil Musatov	Theorems about space-bounded Kolmogorov complexity obtained by "naive" derandomization	CoRR	2010	DBLP BibTeX RDF
1	Ronen Shaltiel	Typically-correct derandomization.	SIGACT News	2010	DBLP DOI BibTeX RDF
1	Eric Allender, Vikraman Arvind, Fengming Wang	Uniform Derandomization from Pathetic Lower Bounds.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff	Derandomizing from Random Strings.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	Truth-table Reducibility, Kolmogorov Complexity, Derandomization
1	Matt DeVos, Ariel Gabizon	Simple Affine Extractors Using Dimension Expansion.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness
1	Dan Gutfreund, Akinori Kawachi	Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting
1	Ronen Shaltiel	Derandomized Parallel Repetition Theorems for Free Games.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	Derandomization, Randomness extractors, Parallel repetition
1	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
1	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
1	Anne Auger, Dimo Brockhoff, Nikolaus Hansen	Mirrored variants of the (1, 2)-CMA-ES compared on the noisy BBOB-2010 testbed.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	benchmarking, black-box optimization
1	Anne Auger, Dimo Brockhoff, Nikolaus Hansen	Mirrored variants of the (1, 4)-CMA-ES compared on the noisy BBOB-2010 testbed.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	benchmarking, black-box optimization
1	Anne Auger, Dimo Brockhoff, Nikolaus Hansen	Comparing the (1+1)-CMA-ES with a mirrored (1+2)-CMA-ES with sequential selection on the noiseless BBOB-2010 testbed.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	benchmarking, black-box optimization
1	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
1	Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz	A New Derandomization of Auctions.	SAGT	2009	DBLP DOI BibTeX RDF
1	Ronen Shaltiel	Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.	IEEE Conference on Computational Complexity	2009	DBLP DOI BibTeX RDF
1	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
1	Neeraj Kayal, Shubhangi Saraf	Blackbox Polynomial Identity Testing for Depth 3 Circuits.	FOCS	2009	DBLP DOI BibTeX RDF	Sylvester, Derandomization, Arithmetic circuits
1	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
1	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
1	Christopher Umans	Reconstructive Dispersers and Hitting Set Generators.	Algorithmica	2009	DBLP DOI BibTeX RDF	Hitting set generator, Derandomization, Disperser
1	Zeev Dvir, Ariel Gabizon, Avi Wigderson	Extractors And Rank Extractors For Polynomial Sources.	Computational Complexity	2009	DBLP DOI BibTeX RDF	Derandomization, Extractors
1	Raghu Meka, David Zuckerman	Small-Bias Spaces for Group Products.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Andrzej Lingas	A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication.	ESA	2009	DBLP DOI BibTeX RDF
1	George Karakostas	General Pseudo-random Generators from Weaker Models of Computation.	ISAAC	2009	DBLP DOI BibTeX RDF	monotone circuit complexity, circuit complexity, Pseudo-random generators
1	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Computational Complexity	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
1	Omer Reingold	Undirected connectivity in log-space.	J. ACM	2008	DBLP DOI BibTeX RDF	bounded space algorithms, Derandomization, pseudorandom generator
1	Parikshit Gopalan, Venkatesan Guruswami	Hardness Amplification within NP against Deterministic Algorithms.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	Hardness Amplication, Error-Correcting Codes, Derandomization, NP
1	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
1	Zeev Dvir, Amir Shpilka, Amir Yehudayoff	Hardness-randomness tradeoffs for bounded depth arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds, arithmetic circuits
1	Lance Fortnow, Rahul Santhanam	Infeasibility of instance compression and succinct PCPs for NP.	STOC	2008	DBLP DOI BibTeX RDF	instance compression, succinct PCPs, cryptography, parameterized complexity, polynomial hierarchy
1	Manindra Agrawal, V. Vinay	Arithmetic Circuits: A Chasm at Depth Four.	FOCS	2008	DBLP DOI BibTeX RDF
1	Luqing Wang, Chintha Tellambura	Clipping-Noise Guided Sign-Selection for PAR Reduction in OFDM Systems.	IEEE Transactions on Signal Processing	2008	DBLP DOI BibTeX RDF
1	Luqing Wang, Chintha Tellambura	Cross-Entropy-Based Sign-Selection Algorithms for Peak-to-Average Power Ratio Reduction of OFDM Systems.	IEEE Transactions on Signal Processing	2008	DBLP DOI BibTeX RDF
1	Vikraman Arvind, Partha Mukhopadhyay	Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Xiaoyang Gu, Jack H. Lutz	Dimension Characterizations of Complexity Classes.	Computational Complexity	2008	DBLP DOI BibTeX RDF	Subject classification, 68Q15
1	Aduri Pavan, N. V. Vinodchandran	Relations between Average-Case and Worst-Case Complexity.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Average-case complexity, Arthur-Merlin games, Worst-case complexity
1	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
1	Boaz Barak, Shien Jin Ong, Salil P. Vadhan	Derandomization in Cryptography.	SIAM J. Comput.	2007	DBLP DOI BibTeX RDF
1	Ilia Binder, Mark Braverman	Derandomization of Euclidean Random Walks.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
1	Qi Cheng	Derandomization of Sparse Cyclotomic Integer Zero Testing.	FOCS	2007	DBLP DOI BibTeX RDF
1	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
1	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
1	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
1	Jianer Chen, Songjian Lu, Sing-Hoi Sze, Fenghui Zhang	Improved algorithms for path, matching, and packing problems.	SODA	2007	DBLP DOI BibTeX RDF
1	Andris Ambainis, Joseph Emerson	Quantum t-designs: t-wise Independence in the Quantum World.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
1	Shankar Kalyanaraman, Christopher Umans	Algorithms for Playing Games with Limited Randomness.	ESA	2007	DBLP DOI BibTeX RDF
1	Peng Cui	A Tighter Analysis of Set Cover Greedy Algorithm for Test Set.	ESCAPE	2007	DBLP DOI BibTeX RDF