Search results for "Derandomization"

Hits ?▲	Authors	Title	Venue	Year	Link
20	Daniel J. Bernstein	On the looseness of FO derandomization.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
20	Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan	Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.	SIAM J. Comput.	2021	DBLP DOI BibTeX RDF
20	Pranjal Dutta, Nitin Saxena 0001, Thomas Thierauf	A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization.	ITCS	2021	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001	Network Decomposition and Distributed Derandomization.	ICDCN	2021	DBLP DOI BibTeX RDF
20	Pranjal Dutta	Real τ-Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization.	CSR	2021	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Roei Tell	Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost.	STOC	2021	DBLP DOI BibTeX RDF
20	Zander Kelley	An improved derandomization of the switching lemma.	STOC	2021	DBLP DOI BibTeX RDF
20	William M. Hoza	Better Pseudodistributions and Derandomization for Space-Bounded Computation.	APPROX-RANDOM	2021	DBLP DOI BibTeX RDF
20	Pranjal Dutta, Nitin Saxena 0001, Thomas Thierauf	Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Lijie Chen 0001, Roei Tell	Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Kuan Cheng, William Hoza	Hitting Sets Give Two-Sided Derandomization of Small Space.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Lijie Chen 0001, Xin Lyu 0002, Ryan Williams 0001	Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Zander Kelley	An Improved Derandomization of the Switching Lemma.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Lijie Chen 0001, Hanlin Ren	Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
20	Yi-Jun Chang, Thatchaphol Saranurak	Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization.	CoRR	2020	DBLP BibTeX RDF
20	S. Cliff Liu	Simpler Partial Derandomization of PPSZ for $k$-SAT.	CoRR	2020	DBLP BibTeX RDF
20	Ofer Grossman, Dana Moshkovitz	Amplification and Derandomization without Slowdown.	SIAM J. Comput.	2020	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Ron D. Rothblum, Roei Tell, Eylon Yogev	On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.	FOCS	2020	DBLP DOI BibTeX RDF
20	Yi-Jun Chang, Thatchaphol Saranurak	Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization.	FOCS	2020	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Xin Lyu 0002, R. Ryan Williams	Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.	FOCS	2020	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001	Network Decomposition and Distributed Derandomization (Invited Paper).	SIROCCO	2020	DBLP DOI BibTeX RDF
20	Václav Rozhon, Mohsen Ghaffari 0001	Polylogarithmic-time deterministic network decomposition and distributed derandomization.	STOC	2020	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Hanlin Ren	Strong average-case lower bounds from non-trivial derandomization.	STOC	2020	DBLP DOI BibTeX RDF
20	Kuan Cheng, William M. Hoza	Hitting Sets Give Two-Sided Derandomization of Small Space.	CCC	2020	DBLP DOI BibTeX RDF
20	Jeffrey Negrea, Gintare Karolina Dziugaite, Daniel M. Roy 0001	In Defense of Uniform Convergence: Generalization via Derandomization with an Application to Interpolating Predictors.	ICML	2020	DBLP BibTeX RDF
20	Roei Tell	Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials.	Comput. Complex.	2019	DBLP DOI BibTeX RDF
20	Lijie Chen 0001, Ron Rothblum, Roei Tell, Eylon Yogev	On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
20	Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon	Derandomization from Algebraic Hardness: Treading the Borders.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
20	Jeffrey Negrea, Gintare Karolina Dziugaite, Daniel M. Roy 0001	In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors.	CoRR	2019	DBLP BibTeX RDF
20	Orit E. Raz, Avi Wigderson	Subspace arrangements, graph rigidity and derandomization through submodular optimization.	CoRR	2019	DBLP BibTeX RDF
20	Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon	Derandomization from Algebraic Hardness: Treading the Borders.	CoRR	2019	DBLP BibTeX RDF
20	Václav Rozhon, Mohsen Ghaffari 0001	Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization.	CoRR	2019	DBLP BibTeX RDF
20	Guy Blanc, Jane Lange, Li-Yang Tan	Constructive derandomization of query algorithms.	CoRR	2019	DBLP BibTeX RDF
20	Pascal Koiran, Mateusz Skomra	Derandomization and absolute reconstruction for sums of powers of linear forms.	CoRR	2019	DBLP BibTeX RDF
20	Gilad Asharov, Naomi Ephraim, Ilan Komargodski, Rafael Pass	On Perfect Correctness without Derandomization.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
20	Zeyu Guo 0001, Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon	Derandomization from Algebraic Hardness: Treading the Borders.	FOCS	2019	DBLP DOI BibTeX RDF
20	Moses Ganardi, Danny Hucke, Markus Lohrey	Derandomization for Sliding Window Algorithms with Strict Correctness.	CSR	2019	DBLP DOI BibTeX RDF
20	William M. Hoza	Typically-Correct Derandomization for Small Time and Space.	CCC	2019	DBLP DOI BibTeX RDF
20	Christophe Hauser, Jayakrishna Menon, Yan Shoshitaishvili, Ruoyu Wang 0001, Giovanni Vigna, Christopher Kruegel	Sleak: automating address space layout derandomization.	ACSAC	2019	DBLP DOI BibTeX RDF
20	Xiaoli Luan, Peng Shi 0001, Fei Liu 0001	Given-time multiple frequency control for Markov jump systems based on derandomization.	Inf. Sci.	2018	DBLP DOI BibTeX RDF
20	Marco Carmosino, Russell Impagliazzo, Manuel Sabin	Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
20	Valentine Kabanets, Zhenjian Lu	Satisfiability and Derandomization for Small Polynomial Threshold Circuits.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
20	Marvin Künnemann	On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.	CoRR	2018	DBLP BibTeX RDF
20	Dan Gordon 0001	A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates.	Numer. Algorithms	2018	DBLP DOI BibTeX RDF
20	Lior Rotem, Gil Segev 0001	Injective Trapdoor Functions via Derandomization: How Strong is Rudich's Black-Box Barrier?	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
20	Daniel Minahan, Ilya Volkovich	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.	ACM Trans. Comput. Theory	2018	DBLP DOI BibTeX RDF
20	Lior Rotem, Gil Segev 0001	Injective Trapdoor Functions via Derandomization: How Strong is Rudich's Black-Box Barrier?	TCC (1)	2018	DBLP DOI BibTeX RDF
20	Marvin Künnemann	On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.	ESA	2018	DBLP DOI BibTeX RDF
20	Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin	Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity.	ICALP	2018	DBLP DOI BibTeX RDF
20	Roei Tell	Quantified derandomization of linear threshold circuits.	STOC	2018	DBLP DOI BibTeX RDF
20	Valentine Kabanets, Zhenjian Lu	Satisfiability and Derandomization for Small Polynomial Threshold Circuits.	APPROX-RANDOM	2018	DBLP DOI BibTeX RDF
20	Anton Malyshev, Igor Pak	Lifts, derandomization, and diameters of Schreier graphs of Mealy automata.	Comb.	2017	DBLP DOI BibTeX RDF
20	Roei Tell	Quantified derandomization of linear threshold circuits.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
20	Roei Tell	A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
20	Mathieu Gerber, Luke Bornn	Improving simulated annealing through derandomization.	J. Glob. Optim.	2017	DBLP DOI BibTeX RDF
20	Donald M. Stull	Some Results on Circuit Lower Bounds and Derandomization of Arthur-Merlin Problems.	CoRR	2017	DBLP BibTeX RDF
20	Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan	Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.	CoRR	2017	DBLP BibTeX RDF
20	William M. Hoza	Typically-Correct Derandomization for Small Time and Space.	CoRR	2017	DBLP BibTeX RDF
20	Roei Tell	Quantified Derandomization of Linear Threshold Circuits.	CoRR	2017	DBLP BibTeX RDF
20	Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan	Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.	FOCS	2017	DBLP DOI BibTeX RDF
20	Nir Bitansky, Vinod Vaikuntanathan	A Note on Perfect Correctness by Derandomization.	EUROCRYPT (2)	2017	DBLP DOI BibTeX RDF
20	Hiroki Oshima	Derandomization for k-Submodular Maximization.	IWOCA	2017	DBLP DOI BibTeX RDF
20	Daniel Minahan, Ilya Volkovich	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.	CCC	2017	DBLP DOI BibTeX RDF
20	Roei Tell	Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials.	CCC	2017	DBLP DOI BibTeX RDF
20	Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization.	Encyclopedia of Algorithms	2016	DBLP DOI BibTeX RDF
20	Dominik Scheder	Derandomization of $\boldsymbol{k}$ -SAT Algorithm.	Encyclopedia of Algorithms	2016	DBLP DOI BibTeX RDF
20	Daniel Minahan, Ilya Volkovich	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
20	Roei Tell	Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
20	Hiroki Oshima	Derandomization for k-submodular maximization.	CoRR	2016	DBLP BibTeX RDF
20	R. Ryan Williams	Natural Proofs versus Derandomization.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
20	Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
20	Ofer Grossman, Dana Moshkovitz	Amplification and Derandomization without Slowdown.	FOCS	2016	DBLP DOI BibTeX RDF
20	Nir Bitansky, Vinod Vaikuntanathan	A Note on Perfect Correctness by Derandomization.	Electron. Colloquium Comput. Complex.	2015	DBLP BibTeX RDF
20	Ofer Grossman, Dana Moshkovitz	Amplification and Derandomization Without Slowdown.	Electron. Colloquium Comput. Complex.	2015	DBLP BibTeX RDF
20	Ofer Grossman, Dana Moshkovitz	Amplification and Derandomization Without Slowdown.	CoRR	2015	DBLP BibTeX RDF
20	Nir Bitansky, Vinod Vaikuntanathan	A Note on Perfect Correctness by Derandomization.	IACR Cryptol. ePrint Arch.	2015	DBLP BibTeX RDF
20	Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz	Hats, auctions and derandomization.	Random Struct. Algorithms	2015	DBLP DOI BibTeX RDF
20	Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova	Tighter Connections between Derandomization and Circuit Lower Bounds.	APPROX-RANDOM	2015	DBLP DOI BibTeX RDF
20	Daniil Musatov	Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization.	Theory Comput. Syst.	2014	DBLP DOI BibTeX RDF
20	Jirí Wiedermann	Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds' Algorithm.	IFIP TCS	2014	DBLP DOI BibTeX RDF
20	Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.	CoRR	2013	DBLP BibTeX RDF
20	David Gross 0003, Felix Krahmer, Richard Kueng	A Partial Derandomization of PhaseLift using Spherical Designs.	CoRR	2013	DBLP BibTeX RDF
20	Zheng Wang 0013, Shuiyin Liu, Cong Ling 0001	Decoding by Sampling II: Derandomization and Soft-output Decoding	CoRR	2013	DBLP BibTeX RDF
20	Zheng Wang 0013, Shuiyin Liu, Cong Ling 0001	Decoding by Sampling - Part II: Derandomization and Soft-Output Decoding.	IEEE Trans. Commun.	2013	DBLP DOI BibTeX RDF
20	Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.	FOCS	2013	DBLP DOI BibTeX RDF
20	Ryan Williams 0001	Natural proofs versus derandomization.	STOC	2013	DBLP DOI BibTeX RDF
20	Luca Trevisan, Tongke Xue	A Derandomized Switching Lemma and an Improved Derandomization of AC0.	CCC	2013	DBLP DOI BibTeX RDF
20	Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel	Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.	Comput. Complex.	2012	DBLP DOI BibTeX RDF
20	George Karakostas, Jeff Kinne, Dieter van Melkebeek	On derandomization and average-case complexity of monotone functions.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
20	Luca Trevisan	A Derandomized Switching Lemma and an Improved Derandomization of AC0.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
20	Ryan Williams 0001	Natural Proofs Versus Derandomization	CoRR	2012	DBLP BibTeX RDF
20	Thomas Müller-Gronbach, Klaus Ritter 0001, Larisa Yaroslavtseva	Derandomization of the Euler scheme for scalar stochastic differential equations.	J. Complex.	2012	DBLP DOI BibTeX RDF
20	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
20	Luca Trevisan	Pseudorandomness and derandomization.	XRDS	2012	DBLP DOI BibTeX RDF
20	Ronen Shaltiel	Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.	Comput. Complex.	2011	DBLP DOI BibTeX RDF
20	Scott Aaronson, Dieter van Melkebeek	On Circuit Lower Bounds from Derandomization.	Theory Comput.	2011	DBLP DOI BibTeX RDF
20	Linqing Tang	On the derandomization of the graph test for homomorphism over groups.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
20	Mahdi Cheraghchi	Applications of Derandomization Theory in Coding	CoRR	2011	DBLP BibTeX RDF
20	Ankur Sahai	Derandomization of Online Assignment Algorithms for Dynamic Graphs	CoRR	2011	DBLP BibTeX RDF
20	Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan 0001	Derandomization of auctions.	Games Econ. Behav.	2011	DBLP DOI BibTeX RDF