Search results for "dispersers"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
109	Eli Ben-Sasson, Swastik Kopparty	Affine dispersers from subspace polynomials.	STOC	2009	DBLP DOI BibTeX RDF	randomness, extractors
109	Ariel Gabizon, Ronen Shaltiel	Increasing the Output Length of Zero-Error Dispersers.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
90	Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel	Streaming Computation of Combinatorial Objects.	CCC	2002	DBLP DOI BibTeX RDF	error-correcting codes, extractors, dispersers, streaming computation, universal hash functions, online computation
76	Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson	Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.	STOC	2005	DBLP DOI BibTeX RDF	dispersers condenser, constructions, extractors, explicit, ramsey graphs
61	David Zuckerman	Linear degree extractors and the inapproximability of max clique and chromatic number.	STOC	2006	DBLP DOI BibTeX RDF	approximation, NP-hard, clique, extractor, pseudorandom, disperser, chromatic number, explicit construction
61	Noam Nisan	Extracting Randomness: How and Why A survey.	CCC	1996	DBLP DOI BibTeX RDF	Randmoness, Computational Complexity, Derandomization, Expanders
56	Boaz Barak, Anup Rao 0001, Ronen Shaltiel, Avi Wigderson	2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.	STOC	2006	DBLP DOI BibTeX RDF	independent sources, extractors, dispersers, Ramsey graphs
56	Aviad Cohen 0001, Avi Wigderson	Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	weak bit fixing sources, RP algorithm, BPP algorithm, deterministic amplification, bipartite multigraphs, probabilistic algorithms, dispersers, error probability, weak random sources
49	Christopher Umans	Hardness of Approximating Sigma2p Minimization Problems.	FOCS	1999	DBLP DOI BibTeX RDF	computational complexity, hardness of approximation, logic minimization, dispersers, polynomial hierarchy
48	Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma	On the Error Parameter of Dispersers.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
48	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
41	Boaz Barak, Russell Impagliazzo, Avi Wigderson	Extracting Randomness Using Few Independent Sources.	FOCS	2004	DBLP DOI BibTeX RDF
28	Gil Cohen	Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs.	SIAM J. Comput.	2021	DBLP DOI BibTeX RDF
28	Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma	Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
28	Xue Chen	Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders.	SODA	2016	DBLP DOI BibTeX RDF
28	Alexander Golovnev, Alexander S. Kulikov	Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds.	ITCS	2016	DBLP DOI BibTeX RDF
28	Gil Cohen	Two-source dispersers for polylogarithmic entropy and improved ramsey graphs.	STOC	2016	DBLP DOI BibTeX RDF
28	Gil Cohen	Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs.	Electron. Colloquium Comput. Complex.	2015	DBLP BibTeX RDF
28	Alexander Golovnev, Alexander S. Kulikov	Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.	Electron. Colloquium Comput. Complex.	2015	DBLP BibTeX RDF
28	Gil Cohen	Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs.	CoRR	2015	DBLP BibTeX RDF
28	Xue Chen	Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders.	CoRR	2015	DBLP BibTeX RDF
28	Raghu Meka, Omer Reingold, Yuan Zhou 0007	Deterministic Coupon Collection and Better Strong Dispersers.	APPROX-RANDOM	2014	DBLP DOI BibTeX RDF
28	Ariel Gabizon, Ronen Shaltiel	Increasing the output length of zero-error dispersers.	Random Struct. Algorithms	2012	DBLP DOI BibTeX RDF
28	Eli Ben-Sasson, Swastik Kopparty	Affine Dispersers from Subspace Polynomials.	SIAM J. Comput.	2012	DBLP DOI BibTeX RDF
28	Ariel Gabizon, Ronen Shaltiel	Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors.	APPROX-RANDOM	2012	DBLP DOI BibTeX RDF
28	Ronen Shaltiel	Dispersers for affine sources with sub-polynomial entropy.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
28	Evgeny Demenkov, Alexander S. Kulikov	An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
28	Ronen Shaltiel	Dispersers for Affine Sources with Sub-polynomial Entropy.	FOCS	2011	DBLP DOI BibTeX RDF
28	Evgeny Demenkov, Alexander S. Kulikov	An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.	MFCS	2011	DBLP DOI BibTeX RDF
28	Xin Li 0006	A New Approach to Affine Extractors and Dispersers.	CCC	2011	DBLP DOI BibTeX RDF
28	Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson	Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors.	J. ACM	2010	DBLP DOI BibTeX RDF
28	Eli Ben-Sasson, Swastik Kopparty	Affine Dispersers from Subspace Polynomials.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
28	Xin Li 0006	A New Approach to Affine Extractors and Dispersers.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
28	Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson	Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
28	Christopher Umans	Reconstructive Dispersers and Hitting Set Generators.	Algorithmica	2009	DBLP DOI BibTeX RDF	Hitting set generator, Derandomization, Disperser
28	Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma	On the Error Parameter of Dispersers	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
28	Christopher Umans	Reconstructive Dispersers and Hitting Set Generators.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
28	Amnon Ta-Shma	Almost Optimal Dispersers.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 68Q01, 68R10
28	Jaikumar Radhakrishnan, Amnon Ta-Shma	Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.	SIAM J. Discret. Math.	2000	DBLP DOI BibTeX RDF
28	Amnon Ta-Shma	Almost Optimal Dispersers.	STOC	1998	DBLP DOI BibTeX RDF
28	Michael E. Saks, Aravind Srinivasan, Shiyu Zhou	Explicit dispersers with polylog degree.	STOC	1995	DBLP DOI BibTeX RDF
20	Eran Rom, Amnon Ta-Shma	Improving the Alphabet-Size in Expander-Based Code Constructions.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
20	Christopher Umans	Optimization Problems in the Polynomial-Time Hierarchy.	TAMC	2006	DBLP DOI BibTeX RDF
20	Anup Rao 0001	Extractors for a constant number of polynomially small min-entropy independent sources.	STOC	2006	DBLP DOI BibTeX RDF	independent sources, extractor, Ramsey graphs
20	Amnon Ta-Shma, Christopher Umans, David Zuckerman	Loss-less condensers, unbalanced expanders, and extractors.	STOC	2001	DBLP DOI BibTeX RDF
20	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
20	Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano	On the Complexity of Wavelength Converters.	MFCS	1998	DBLP DOI BibTeX RDF
20	Jaikumar Radhakrishnan, Amnon Ta-Shma	Tight Bounds for Depth-two Superconcentrators.	FOCS	1997	DBLP DOI BibTeX RDF	depth-two superconcentrators, optimal bounds, disperser graphs, entropy loss, superconcentrator, entropy, directed graphs, directed graph, edges, tight bounds