Search results for "derandomization"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
67	D. Sivakumar	Algorithmic Derandomization via Complexity Theory.	CCC	2002	DBLP DOI BibTeX RDF	Johnson-Lindenstrauss Lemma, Derandomization, randomized rounding
67	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
62	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators and Typically-Correct Derandomization.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
62	Chi-Jen Lu	Derandomizing Arthur-Merlin games under uniform assumptions.	Comput. Complex.	2001	DBLP DOI BibTeX RDF	graph nonisomorphism problem, nondeterminism, Derandomization, uniformity, Arthur-Merlin games
62	Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson	Near-Optimal Conversion of Hardness into Pseudo-Randomness.	FOCS	1999	DBLP DOI BibTeX RDF	Pseudo-Ranndom Generators, Derandomization
57	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
53	Olivier Teytaud, Sylvain Gelly	DCMA: yet another derandomization in covariance-matrix-adaptation.	GECCO	2007	DBLP DOI BibTeX RDF	quasi-random, evolution strategies, derandomization
53	Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan 0001	Derandomization of auctions.	STOC	2005	DBLP DOI BibTeX RDF	auctions, mechanism design, derandomization
48	H. Venkateswaran	Derandomization of Probabilistic Auxiliary Pushdown Automata Classes.	CCC	2006	DBLP DOI BibTeX RDF
48	Ankur Bhargava, S. Rao Kosaraju	Derandomization of Dimensionality Reduction and SDP Based Algorithms.	WADS	2005	DBLP DOI BibTeX RDF
48	Rahul Santhanam, Dieter van Melkebeek	Holographic Proofs and Derandomization.	CCC	2003	DBLP DOI BibTeX RDF
48	D. Sivakumar	Algorithmic derandomization via complexity theory.	STOC	2002	DBLP DOI BibTeX RDF
48	Eric Allender	When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity.	FSTTCS	2001	DBLP DOI BibTeX RDF
48	Bernard Chazelle	Irregularities of Distribution, Derandomization, and Complexity Theory.	FSTTCS	2000	DBLP DOI BibTeX RDF
48	Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher	A Derandomization Using Min-Wise Independent Permutations.	RANDOM	1998	DBLP DOI BibTeX RDF
47	Amir Shpilka, Avi Wigderson	Derandomizing homomorphism testing in general groups.	STOC	2004	DBLP DOI BibTeX RDF	homomorphism testing, derandomization, linearity testing
47	Valentine Kabanets	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.	CCC	2000	DBLP DOI BibTeX RDF	probabilistic complexity classes, uniform setting, derandomization
43	Luqing Wang, Chintha Tellambura	Cross-Entropy-Based Sign-Selection Algorithms for Peak-to-Average Power Ratio Reduction of OFDM Systems.	IEEE Trans. Signal Process.	2008	DBLP DOI BibTeX RDF
43	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
43	Anand Srivastav, Peter Stangier	On Quadratic Lattice Approximations.	ISAAC	1993	DBLP DOI BibTeX RDF
39	Lijie Chen 0001, Roei Tell, Ryan Williams 0001	Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
39	Lijie Chen 0001	New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method.	ITCS	2023	DBLP DOI BibTeX RDF
39	Lijie Chen 0001, Roei Tell, Ryan Williams 0001	Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.	FOCS	2023	DBLP DOI BibTeX RDF
39	Lijie Chen 0008	New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
39	Ketan Mulmuley	Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma	CoRR	2012	DBLP BibTeX RDF
39	Ketan Mulmuley	Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma.	FOCS	2012	DBLP DOI BibTeX RDF
38	Hervé Brönnimann, Bernard Chazelle, Jirí Matousek 0001	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
34	Marius Zimand	Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification, 68Q15
34	Moritz Müller	Parameterized Derandomization.	IWPEC	2008	DBLP DOI BibTeX RDF
34	Harry Buhrman, Lance Fortnow, Aduri Pavan	Some Results on Derandomization.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
34	Harry Buhrman, Lance Fortnow, Aduri Pavan	Some Results on Derandomization.	STACS	2003	DBLP DOI BibTeX RDF
34	Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy	Derandomization and Distinguishing Complexity.	CCC	2003	DBLP DOI BibTeX RDF
34	Adam R. Klivans	On the Derandomization of Constant Depth Circuits.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
34	Lance Fortnow	Comparing Notions of Full Derandomization.	CCC	2001	DBLP DOI BibTeX RDF
34	Yijie Han, Yoshihide Igarashi	Parallel PROFIT/COST Algorithms Through Fast Derandomization.	Acta Informatica	1999	DBLP DOI BibTeX RDF
34	Roy Armoni	On the Derandomization of Space-Bounded Computations.	RANDOM	1998	DBLP DOI BibTeX RDF
34	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
33	Gary L. Miller, Donald R. Sheehy	Approximate center points with proofs.	SCG	2009	DBLP DOI BibTeX RDF	Tverberg's theorem, centerpoints, approximation algorithms, derandomization
33	Olivier Teytaud	When Does Quasi-random Work?.	PPSN	2008	DBLP DOI BibTeX RDF	Evolution Strategies, Derandomization
33	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
33	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
33	Benjamin Doerr	Antirandomizing the Wrong Game.	ICALP	2002	DBLP DOI BibTeX RDF	Games, randomization, derandomization
33	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
33	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
29	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
29	Manindra Agrawal, V. Vinay	Arithmetic Circuits: A Chasm at Depth Four.	FOCS	2008	DBLP DOI BibTeX RDF
29	Vikraman Arvind, Partha Mukhopadhyay	Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
29	Vikraman Arvind, Jacobo Torán	Solvable Group Isomorphism.	CCC	2004	DBLP DOI BibTeX RDF
29	Chi-Jen Lu	Derandomizing Arthur-Merlin Games under Uniform Assumptions.	ISAAC	2000	DBLP DOI BibTeX RDF
29	Vojtech Rödl, Andrzej Rucinski 0001, Michelle Wagner	An Algorithmic Embedding of Graphs via Perfect Matchings.	RANDOM	1998	DBLP DOI BibTeX RDF
29	Anand Srivastav, Peter Stangier	Integer Multicommodity Flows with Reduced Demands.	ESA	1993	DBLP DOI BibTeX RDF
20	Yishu Zeng	Derandomization of persuasion mechanisms.	J. Econ. Theory	2023	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Ron D. Rothblum, Roei Tell, Eylon Yogev	On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds.	J. ACM	2023	DBLP DOI BibTeX RDF
20	Dean Doron, Roei Tell	Derandomization with Minimal Memory Footprint.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
20	Yakov Shalunov	Leakage-Resilient Hardness Equivalence to Logspace Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Christoph Grunau, Václav Rozhon	Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence.	CoRR	2023	DBLP DOI BibTeX RDF
20	Ronen Shaltiel, Emanuele Viola	On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
20	Sameep Dahal, Francesco D'Amore 0001, Henrik Lievonen, Timothé Picavet, Jukka Suomela	Distributed derandomization revisited.	CoRR	2023	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Christoph Grunau	Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping.	CoRR	2023	DBLP DOI BibTeX RDF
20	Tianrong Lin	Quantum and Probabilistic Computers Rigorously Powerful than Traditional Computers, and Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
20	Kouhei Nakaji, Suguru Endo, Yuichiro Matsuzaki, Hideaki Hakoshima	Measurement optimization of variational quantum simulation by classical shadow and derandomization.	Quantum	2023	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.	SODA	2023	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Christoph Grunau, Václav Rozhon	Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence.	FOCS	2023	DBLP DOI BibTeX RDF
20	Sameep Dahal, Francesco D'Amore 0001, Henrik Lievonen, Timothé Picavet, Jukka Suomela	Brief Announcement: Distributed Derandomization Revisited.	DISC	2023	DBLP DOI BibTeX RDF
20	Alexander Golovnev, Tom Gur, Igor Shinkar	Derandomization of Cell Sampling.	SOSA	2023	DBLP DOI BibTeX RDF
20	Aaron (Louie) Putterman, Edward Pyne	Near-Optimal Derandomization of Medium-Width Branching Programs.	STOC	2023	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Roei Tell	When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems.	STOC	2023	DBLP DOI BibTeX RDF
20	Dieter van Melkebeek, Nicollas M. Sdroievski	Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols.	FSTTCS	2023	DBLP DOI BibTeX RDF
20	Dean Doron, Roei Tell	Derandomization with Minimal Memory Footprint.	CCC	2023	DBLP DOI BibTeX RDF
20	Sorrachai Yingchareonthawornchai	Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization.		2023	RDF
20	Nir Bitansky, Vinod Vaikuntanathan	A Note on Perfect Correctness by Derandomization.	J. Cryptol.	2022	DBLP DOI BibTeX RDF
20	Kuan Cheng, William M. Hoza	Hitting Sets Give Two-Sided Derandomization of Small Space.	Theory Comput.	2022	DBLP BibTeX RDF
20	Yanyi Liu, Rafael Pass	Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
20	Aaron (Louie) Putterman, Edward Pyne	Near-Optimal Derandomization of Medium-Width Branching Programs.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
20	Samuel Epstein 0001	Derandomization Under Different Resource Constraints.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
20	Lijie Chen 0001, Roei Tell	When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
20	Roei Tell	Quantified Derandomization: How to Find Water in the Ocean.	Found. Trends Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
20	Samuel Epstein 0001	22 Examples of Solution Compression via Derandomization.	CoRR	2022	DBLP DOI BibTeX RDF
20	Samuel Epstein 0001	Derandomization under Different Resource Constraints.	CoRR	2022	DBLP DOI BibTeX RDF
20	Jimmy Wu, Yatong Chen, Yang Liu	Metric-Fair Classifier Derandomization.	CoRR	2022	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.	CoRR	2022	DBLP DOI BibTeX RDF
20	Nir Bitansky, Sapir Freizeit	Statistically Sender-Private OT from LPN and Derandomization.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
20	Lijie Chen 0001, Hanlin Ren	Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
20	Zeyu Guo 0001, Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon	Derandomization from Algebraic Hardness.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
20	Ronen Shaltiel, Emanuele Viola	On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.	ITCS	2022	DBLP DOI BibTeX RDF
20	Nir Bitansky, Sapir Freizeit	Statistically Sender-Private OT from LPN and Derandomization.	CRYPTO (3)	2022	DBLP DOI BibTeX RDF
20	Pranav Bisht, Nitin Saxena 0001	Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials.	FSTTCS	2022	DBLP DOI BibTeX RDF
20	Yanyi Liu, Rafael Pass	Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity.	CCC	2022	DBLP DOI BibTeX RDF
20	Oliver Korten	Derandomization from Time-Space Tradeoffs.	CCC	2022	DBLP DOI BibTeX RDF
20	Jimmy Wu, Yatong Chen, Yang Liu	Metric-Fair Classifier Derandomization.	ICML	2022	DBLP BibTeX RDF
20	Lior Rotem, Gil Segev 0001	Injective Trapdoor Functions via Derandomization: How Strong is Rudich's Black-Box Barrier?	J. Cryptol.	2021	DBLP DOI BibTeX RDF
20	Pascal Koiran, Mateusz Skomra	Derandomization and absolute reconstruction for sums of powers of linear forms.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
20	Ronen Shaltiel, Emanuele Viola	On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
20	William Hoza	Better Pseudodistributions and Derandomization for Space-Bounded Computation.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
20	Roei Tell	How to Find Water in the Ocean: A Survey on Quantified Derandomization.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
20	Moses Ganardi, Danny Hucke, Markus Lohrey	Derandomization for Sliding Window Algorithms with Strict Correctness∗.	Theory Comput. Syst.	2021	DBLP DOI BibTeX RDF
20	Paul Viallard, Pascal Germain, Amaury Habrard, Emilie Morvant	A General Framework for the Derandomization of PAC-Bayesian Bounds.	CoRR	2021	DBLP BibTeX RDF
20	Hsin-Yuan Huang, Richard Kueng, John Preskill	Efficient estimation of Pauli observables by derandomization.	CoRR	2021	DBLP BibTeX RDF
20	Alexander Golovnev, Tom Gur, Igor Shinkar	Derandomization of Cell Sampling.	CoRR	2021	DBLP BibTeX RDF
20	Laurent Feuilloley, Pierre Fraigniaud	Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings.	ACM Trans. Parallel Comput.	2021	DBLP DOI BibTeX RDF