On the public citation graph

Pseudorandom Generators without the XOR Lemma

https://doi.org/10.1006/jcss.2000.1730

0 signed · 388 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/(sici)1098-2418(199712)11:4<345::aid-rsa4>3.0.co;2-zopenalex-snapshot

Randomness-optimal oblivious sampling

inferredcites →https://doi.org/10.1006/jcom.1997.0439openalex-snapshot

Decoding of Reed Solomon Codes beyond the Error-Correction Bound

inferredcites →https://doi.org/10.1006/jcss.1996.0004openalex-snapshot

Randomness is Linear in Space

inferredcites →https://doi.org/10.1006/jcss.1997.1494openalex-snapshot

Natural Proofs

inferredcites →https://doi.org/10.1006/jcss.1997.1546openalex-snapshot

Extracting Randomness: A Survey and New Constructions

inferredcites →https://doi.org/10.1007/3-540-27477-4_16openalex-snapshot

The Complexity of Boolean Functions

inferredcites →https://doi.org/10.1007/3-540-39799-x_37openalex-snapshot

How to Reduce your Enemy’s Information (extended abstract)

inferredcites →https://doi.org/10.1007/3-540-49116-3_8openalex-snapshot

On the Hardness of Permanent

inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot

Hiding instances in multioracle queries

inferredcites →https://doi.org/10.1007/3-540-63165-8_175openalex-snapshot

Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs

inferredcites →https://doi.org/10.1007/978-3-0348-8645-1_7openalex-snapshot

Elements of Information Theory

inferredcites →https://doi.org/10.1007/978-3-662-12521-2openalex-snapshot

Modern Cryptography, Probabilistic Proofs and Pseudorandomness

inferredcites →https://doi.org/10.1007/bf01262928openalex-snapshot

On the hardness of computing the permanent of random matrices

inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

inferredcites →https://doi.org/10.1007/bf01940870openalex-snapshot

Simulating BPP using a general weak random source

inferredcites →https://doi.org/10.1007/bfb0058034openalex-snapshot

On resource-bounded measure and pseudorandomness

inferredcites →https://doi.org/10.1016/0020-0190(92)90014-mopenalex-snapshot

Special subgraphs of weighted visibility graphs

inferredcites →https://doi.org/10.1016/0020-0190(92)90195-2openalex-snapshot

Highly resilient correctors for polynomials

inferredcites →https://doi.org/10.1016/0022-0000(84)90070-9openalex-snapshot

Probabilistic encryption

inferredcites →https://doi.org/10.1016/0885-064x(89)90015-0openalex-snapshot

On the power of two-point based sampling

inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot

Hardness vs randomness

inferredcites →https://doi.org/10.1090/dimacs/002/13openalex-snapshot

New directions in testing

inferredcites →https://doi.org/10.1109/18.782097openalex-snapshot

Improved decoding of Reed-Solomon and algebraic-geometry codes

inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot

Two theorems on random polynomial time

inferredcites →https://doi.org/10.1109/sfcs.1982.45openalex-snapshot

Theory and application of trapdoor functions

inferredcites →https://doi.org/10.1109/sfcs.1985.55openalex-snapshot

The bit extraction problem or t-resilient functions

inferredcites →https://doi.org/10.1109/sfcs.1989.63449openalex-snapshot

Dispersers, deterministic amplification, and weak random sources

inferredcites →https://doi.org/10.1109/sfcs.1992.267760openalex-snapshot

On the bit extraction problem

inferredcites →https://doi.org/10.1109/sfcs.1995.492584openalex-snapshot

Hard-core distributions for somewhat hard problems

inferredcites →https://doi.org/10.1109/sfcs.1998.743524openalex-snapshot

Randomness vs. time: de-randomization under a uniform assumption

inferredcites →https://doi.org/10.1137/0213053openalex-snapshot

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

inferredcites →https://doi.org/10.1137/0222061openalex-snapshot

Random-Self-Reducibility of Complete Sets

inferredcites →https://doi.org/10.1137/s0097539700389652openalex-snapshot

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

inferredcites →https://doi.org/10.1137/s0097539793244708openalex-snapshot

A Pseudorandom Generator from any One-way Function

inferredcites →https://doi.org/10.1137/s0097539796297577openalex-snapshot

Reconstructing Algebraic Functions from Mixed Data

inferredcites →https://doi.org/10.1137/s009753979630091xopenalex-snapshot

Computing with Very Weak Random Sources

inferredcites →https://doi.org/10.1145/103418.103429openalex-snapshot

Self-testing/correcting for polynomials and for approximate functions

inferredcites →https://doi.org/10.1145/22145.22186openalex-snapshot

Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources

inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot

P = BPP if E requires exponential circuits

inferredcites →https://doi.org/10.1145/258533.258642openalex-snapshot

Improved low-degree testing and its applications

inferredcites →https://doi.org/10.1145/301250.301289openalex-snapshot

Construction of extractors using pseudo-random generators (extended abstract)

inferredcites →https://doi.org/10.1145/301250.301397openalex-snapshot

Pseudorandom generators without the XOR Lemma (extended abstract)

inferredcites →https://doi.org/10.1145/335305.335306openalex-snapshot

Extractors and pseudo-random generators with optimal seed length

inferredcites →https://doi.org/10.1145/3749740.3749746openalex-snapshot

A Theory of the Learnable

inferredcites →https://doi.org/10.1145/6490.6503openalex-snapshot

How to construct random functions

inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot

A hard-core predicate for all one-way functions

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/rsa.20498openalex-snapshot

A combination of testability and decodability by tensor products

inferred← citeshttps://doi.org/10.1002/rsa.20652openalex-snapshot

Constructing near spanning trees with few local inspections

inferred← citeshttps://doi.org/10.1002/rsa.21031openalex-snapshot

Erasures versus errors in local decoding and property testing

inferred← citeshttps://doi.org/10.1006/jcss.1999.1646openalex-snapshot

Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds

inferred← citeshttps://doi.org/10.1007/11538462_39openalex-snapshot

Reconstructive Dispersers and Hitting Set Generators

inferred← citeshttps://doi.org/10.1007/11590156_2openalex-snapshot

Computational Complexity Since 1980

inferred← citeshttps://doi.org/10.1007/11830924_35openalex-snapshot

Local Decoding and Testing for Homomorphisms

inferred← citeshttps://doi.org/10.1007/11830924_36openalex-snapshot

Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

inferred← citeshttps://doi.org/10.1007/11944836_12openalex-snapshot

On Obtaining Pseudorandomness from Error-Correcting Codes

inferred← citeshttps://doi.org/10.1007/11944836_19openalex-snapshot

Some Results on Average-Case Hardness Within the Polynomial Hierarchy

inferred← citeshttps://doi.org/10.1007/3-540-39200-9_12openalex-snapshot

Nearly One-Sided Tests and the Goldreich-Levin Predicate

inferred← citeshttps://doi.org/10.1007/3-540-40996-3_26openalex-snapshot

Derandomizing Arthur-Merlin Games under Uniform Assumptions

inferred← citeshttps://doi.org/10.1007/3-540-44666-4_4openalex-snapshot

Error-Correcting Codes and Pseudorandom Projections

inferred← citeshttps://doi.org/10.1007/3-540-45294-x_1openalex-snapshot

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity

inferred← citeshttps://doi.org/10.1007/3-540-45294-x_6openalex-snapshot

Hard Sets and Pseudo-random Generators for Constant Depth Circuits

inferred← citeshttps://doi.org/10.1007/3-540-45726-7_17openalex-snapshot

Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good

inferred← citeshttps://doi.org/10.1007/978-1-4614-6642-0_4openalex-snapshot

Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_691openalex-snapshot

Large-Treewidth Graph Decompositions

inferred← citeshttps://doi.org/10.1007/978-3-030-17653-2_17openalex-snapshot

Non-Malleable Codes Against Bounded Polynomial Time Tampering

inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_15openalex-snapshot

Worst-Case to Average-Case Reductions for Subclasses of P

inferred← citeshttps://doi.org/10.1007/978-3-030-90453-1_15openalex-snapshot

On Derandomizing Yao’s Weak-to-Strong OWF Construction

inferred← citeshttps://doi.org/10.1007/978-3-031-07085-3_20openalex-snapshot

On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness

inferred← citeshttps://doi.org/10.1007/978-3-031-14791-3_3openalex-snapshot

Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

inferred← citeshttps://doi.org/10.1007/978-3-031-58737-5_14openalex-snapshot

A Direct PRF Construction from Kolmogorov Complexity

inferred← citeshttps://doi.org/10.1007/978-3-031-78011-0_9openalex-snapshot

One-Way Functions and pKt Complexity

inferred← citeshttps://doi.org/10.1007/978-3-032-01855-7_20openalex-snapshot

Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity

inferred← citeshttps://doi.org/10.1007/978-3-319-08783-2_18openalex-snapshot

A New View on Worst-Case to Average-Case Reductions for NP Problems

inferred← citeshttps://doi.org/10.1007/978-3-319-24584-3_74openalex-snapshot

The Design Trends of Keystream Generator for Stream Cipher for High Immunity Attacks

inferred← citeshttps://doi.org/10.1007/978-3-319-58747-9_6openalex-snapshot

Can We Locally Compute Sparse Connected Subgraphs?

inferred← citeshttps://doi.org/10.1007/978-3-319-77404-6_24openalex-snapshot

An Average-Case Lower Bound Against $$\mathsf {ACC}^0$$

inferred← citeshttps://doi.org/10.1007/978-3-540-24638-1_6openalex-snapshot

List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument

inferred← citeshttps://doi.org/10.1007/978-3-540-28628-8_5openalex-snapshot

Complete Classification of Bilinear Hard-Core Functions

inferred← citeshttps://doi.org/10.1007/978-3-540-45167-9_34openalex-snapshot

Learning Arithmetic Circuits via Partial Derivatives

inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_18openalex-snapshot

Computational Analogues of Entropy

inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_18openalex-snapshot

On the Complexity of Hard-Core Set Constructions

inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_23openalex-snapshot

On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR

inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_35openalex-snapshot

Impossibility Results on Weakly Black-Box Hardness Amplification

inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_36openalex-snapshot

The Complexity of Local List Decoding

inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_35openalex-snapshot

Extractors Using Hardness Amplification

inferred← citeshttps://doi.org/10.1007/978-3-642-10631-6_110openalex-snapshot

General Pseudo-random Generators from Weaker Models of Computation

inferred← citeshttps://doi.org/10.1007/978-3-642-14031-0_4openalex-snapshot

On the Hardness against Constant-Depth Linear-Size Circuits

inferred← citeshttps://doi.org/10.1007/978-3-642-14358-8openalex-snapshot

Locally Decodable Codes and Private Information Retrieval Schemes

inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_29openalex-snapshot

Uniform Derandomization from Pathetic Lower Bounds

inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_56openalex-snapshot

Relativized Worlds without Worst-Case to Average-Case Reductions for NP

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_25openalex-snapshot

Symmetric LDPC Codes and Local Testing

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_26openalex-snapshot

Some Recent Results on Local Testing of Sparse Linear Codes

inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_29openalex-snapshot

Local Property Reconstruction and Monotonicity

inferred← citeshttps://doi.org/10.1007/978-3-642-20901-7_18openalex-snapshot

Locally Decodable Codes: A Brief Survey

inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_32openalex-snapshot

Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

inferred← citeshttps://doi.org/10.1007/978-3-642-22953-4_7openalex-snapshot

Computational Randomness from Generalized Hardcore Sets

inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_55openalex-snapshot

A Combination of Testability and Decodability by Tensor Products

inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_16openalex-snapshot

Succinct Permanent Is NEXP-Hard with Many Hard Instances

inferred← citeshttps://doi.org/10.1007/978-3-642-38536-0_15openalex-snapshot

Towards NEXP versus BPP?

inferred← citeshttps://doi.org/10.1007/978-3-642-40328-6_40openalex-snapshot

Randomness-Efficient Curve Samplers

inferred← citeshttps://doi.org/10.1007/b104335openalex-snapshot

List Decoding of Error-Correcting Codes

inferred← citeshttps://doi.org/10.1007/s00026-011-0124-3openalex-snapshot

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

inferred← citeshttps://doi.org/10.1007/s00037-001-8196-9openalex-snapshot

Derandomizing Arthur--Merlin games under uniform assumptions

inferred← citeshttps://doi.org/10.1007/s00037-003-0175-xopenalex-snapshot

Towards proving strong direct product theorems

inferred← citeshttps://doi.org/10.1007/s00037-004-0182-6openalex-snapshot

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1007/s00037-004-0187-1openalex-snapshot

The complexity of constructing pseudorandom generators from hard functions

inferred← citeshttps://doi.org/10.1007/s00037-005-0197-7openalex-snapshot

Derandomizing Arthur–Merlin Games using Hitting Sets

inferred← citeshttps://doi.org/10.1007/s00037-005-0199-5openalex-snapshot

Language compression and pseudorandom generators

inferred← citeshttps://doi.org/10.1007/s00037-007-0218-9openalex-snapshot

Pseudorandomness for Approximate Counting and Sampling

inferred← citeshttps://doi.org/10.1007/s00037-007-0232-yopenalex-snapshot

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

inferred← citeshttps://doi.org/10.1007/s00037-007-0233-xopenalex-snapshot

Pseudorandomness and Average-Case Complexity Via Uniform Reductions

inferred← citeshttps://doi.org/10.1007/s00037-007-0235-8openalex-snapshot

If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances

inferred← citeshttps://doi.org/10.1007/s00037-011-0003-7openalex-snapshot

Complexity of Hard-Core Set Proofs

inferred← citeshttps://doi.org/10.1007/s00037-011-0006-4openalex-snapshot

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao’s Lemma

inferred← citeshttps://doi.org/10.1007/s00037-012-0036-6openalex-snapshot

Pseudorandom Generators for Combinatorial Checkerboards

inferred← citeshttps://doi.org/10.1007/s00037-015-0100-0openalex-snapshot

Mining Circuit Lower Bound Proofs for Meta-Algorithms

inferred← citeshttps://doi.org/10.1007/s00037-016-0128-9openalex-snapshot

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions

inferred← citeshttps://doi.org/10.1007/s00037-016-0151-xopenalex-snapshot

List-Decoding Barnes–Wall Lattices

inferred← citeshttps://doi.org/10.1007/s00037-023-00238-9openalex-snapshot

Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

inferred← citeshttps://doi.org/10.1007/s00037-025-00268-5openalex-snapshot

On Solving Sparse Polynomial Factorization Related Problems

inferred← citeshttps://doi.org/10.1007/s00145-003-0141-4openalex-snapshot

Nearly One-Sided Tests and the Goldreich–Levin Predicate

inferred← citeshttps://doi.org/10.1007/s00224-011-9365-0openalex-snapshot

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

inferred← citeshttps://doi.org/10.1007/s00453-008-9266-zopenalex-snapshot

Reconstructive Dispersers and Hitting Set Generators

inferred← citeshttps://doi.org/10.1007/s00453-008-9272-1openalex-snapshot

On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR

inferred← citeshttps://doi.org/10.1007/s00453-016-0126-yopenalex-snapshot

Local Computation Algorithms for Graphs of Non-constant Degrees

inferred← citeshttps://doi.org/10.1007/s00453-019-00612-6openalex-snapshot

Local Algorithms for Sparse Spanning Graphs

inferred← citeshttps://doi.org/10.1007/s00493-003-0025-0openalex-snapshot

Improved Low-Degree Testing and its Applications

inferred← citeshttps://doi.org/10.1007/s00493-006-0036-8openalex-snapshot

Reducing The Seed Length In The Nisan-Wigderson Generator*

inferred← citeshttps://doi.org/10.1007/s00493-007-0053-2openalex-snapshot

Lossless Condensers, Unbalanced Expanders, And Extractors

inferred← citeshttps://doi.org/10.1007/s00493-014-2715-1openalex-snapshot

Symmetric LDPC codes and local testing

inferred← citeshttps://doi.org/10.1016/j.jcss.2004.01.001openalex-snapshot

Hardness amplification within NP

inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.008openalex-snapshot

Hardness amplification within NP against deterministic algorithms

inferred← citeshttps://doi.org/10.1016/j.jcta.2023.105835openalex-snapshot

Singleton-type bounds for list-decoding and list-recovery, and related results

inferred← citeshttps://doi.org/10.1016/j.tcs.2006.10.009openalex-snapshot

Improved hardness amplification in NP

inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00024-7openalex-snapshot

In search of an easy witness: exponential time vs. probabilistic polynomial time

inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00046-1openalex-snapshot

Pseudo-random generators for all hardnesses

inferred← citeshttps://doi.org/10.1016/s0304-0208(04)80009-4openalex-snapshot

Bibliography

inferred← citeshttps://doi.org/10.1023/a:1022949332276openalex-snapshot

Boosting and Hard-Core Set Construction

inferred← citeshttps://doi.org/10.1090/gsm/142openalex-snapshot

Higher Order Fourier Analysis

inferred← citeshttps://doi.org/10.1090/pcms/010/10openalex-snapshot

Pseudorandomness—Part II

inferred← citeshttps://doi.org/10.1098/rsta.2011.0318openalex-snapshot

Uniform derandomization from pathetic lower bounds

inferred← citeshttps://doi.org/10.1109/ccc.1999.766253openalex-snapshot

Pseudorandom generators without the XOR lemma

inferred← citeshttps://doi.org/10.1109/ccc.1999.766261openalex-snapshot

Proofs, codes, and polynomial-time reducibilities

inferred← citeshttps://doi.org/10.1109/ccc.1999.766263openalex-snapshot

De-randomizing BPP: the state of the art

inferred← citeshttps://doi.org/10.1109/ccc.2002.1004348openalex-snapshot

Pseudorandomness and average-case complexity via uniform reductions

inferred← citeshttps://doi.org/10.1109/ccc.2002.1004350openalex-snapshot

Decoding concatenated codes using soft information

inferred← citeshttps://doi.org/10.1109/ccc.2002.1004354openalex-snapshot

Better lower bounds for locally decodable codes

inferred← citeshttps://doi.org/10.1109/ccc.2003.1214408openalex-snapshot

Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games

inferred← citeshttps://doi.org/10.1109/ccc.2003.1214410openalex-snapshot

Hardness vs. randomness within alternating time

inferred← citeshttps://doi.org/10.1109/ccc.2005.11openalex-snapshot

If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances

inferred← citeshttps://doi.org/10.1109/ccc.2005.16openalex-snapshot

On Constructing Parallel Pseudorandom Generators from One-Way Functions

inferred← citeshttps://doi.org/10.1109/ccc.2005.17openalex-snapshot

On the Complexity of Hardness Amplification

inferred← citeshttps://doi.org/10.1109/ccc.2005.25openalex-snapshot

Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates

inferred← citeshttps://doi.org/10.1109/ccc.2006.26openalex-snapshot

Making Hard Problems Harder

inferred← citeshttps://doi.org/10.1109/ccc.2007.38openalex-snapshot

Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

inferred← citeshttps://doi.org/10.1109/ccc.2008.13openalex-snapshot

Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes

inferred← citeshttps://doi.org/10.1109/ccc.2008.14openalex-snapshot

Noisy Interpolating Sets for Low Degree Polynomials

inferred← citeshttps://doi.org/10.1109/ccc.2008.17openalex-snapshot

Hardness Amplification within NP against Deterministic Algorithms

inferred← citeshttps://doi.org/10.1109/ccc.2009.27openalex-snapshot

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma

inferred← citeshttps://doi.org/10.1109/ccc.2011.38openalex-snapshot

Noisy Interpolation of Sparse Polynomials, and Applications

inferred← citeshttps://doi.org/10.1109/ccc.2012.33openalex-snapshot

List Decoding Barnes-Wall Lattices

inferred← citeshttps://doi.org/10.1109/ccc.2014.34openalex-snapshot

Mining Circuit Lower Bound Proofs for Meta-algorithms

inferred← citeshttps://doi.org/10.1109/focs.2006.13openalex-snapshot

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification

inferred← citeshttps://doi.org/10.1109/focs.2006.18openalex-snapshot

Better lossless condensers through derandomized curve samplers

inferred← citeshttps://doi.org/10.1109/focs.2007.25openalex-snapshot

Hardness Amplification for Errorless Heuristics

inferred← citeshttps://doi.org/10.1109/focs.2007.30openalex-snapshot

Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits

inferred← citeshttps://doi.org/10.1109/focs.2007.31openalex-snapshot

Simulating Quantum Correlations with Finite Communication

inferred← citeshttps://doi.org/10.1109/focs.2007.37openalex-snapshot

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

inferred← citeshttps://doi.org/10.1109/focs.2007.4389512openalex-snapshot

Hardness Amplification for Errorless Heuristics

inferred← citeshttps://doi.org/10.1109/focs.2008.26openalex-snapshot

Locally Testing Direct Product in the Low Error Range

inferred← citeshttps://doi.org/10.1109/focs.2008.60openalex-snapshot

Two Query PCP with Sub-Constant Error

inferred← citeshttps://doi.org/10.1109/focs.2008.90openalex-snapshot

Average-case Complexity

inferred← citeshttps://doi.org/10.1109/focs.2010.71openalex-snapshot

A Fourier-Analytic Approach to Reed-Muller Decoding

inferred← citeshttps://doi.org/10.1109/focs.2010.73openalex-snapshot

Matching Vector Codes

inferred← citeshttps://doi.org/10.1109/focs.2010.88openalex-snapshot

Local List Decoding with a Constant Number of Queries

inferred← citeshttps://doi.org/10.1109/focs.2016.87openalex-snapshot

Amplification and Derandomization without Slowdown

inferred← citeshttps://doi.org/10.1109/focs.2017.27openalex-snapshot

Local List Recovery of High-Rate Tensor Codes & Applications

inferred← citeshttps://doi.org/10.1109/focs.2017.82openalex-snapshot

Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

inferred← citeshttps://doi.org/10.1109/focs.2018.00017openalex-snapshot

Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems

inferred← citeshttps://doi.org/10.1109/focs.2018.00029openalex-snapshot

Improved Decoding of Folded Reed-Solomon and Multiplicity Codes

inferred← citeshttps://doi.org/10.1109/focs.2018.00032openalex-snapshot

Non-Black-Box Worst-Case to Average-Case Reductions within NP

inferred← citeshttps://doi.org/10.1109/focs.2018.00094openalex-snapshot

Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs

inferred← citeshttps://doi.org/10.1109/focs.2019.00065openalex-snapshot

Stoquastic PCP vs. Randomness

inferred← citeshttps://doi.org/10.1109/focs.2019.00079openalex-snapshot

Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits

inferred← citeshttps://doi.org/10.1109/focs46700.2020.00014openalex-snapshot

Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

inferred← citeshttps://doi.org/10.1109/focs46700.2020.00102openalex-snapshot

Nearly Optimal Pseudorandomness From Hardness

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00021openalex-snapshot

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00074openalex-snapshot

Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00075openalex-snapshot

List-Decodability With Large Radius for Reed-Solomon Codes

inferred← citeshttps://doi.org/10.1109/focs54457.2022.00048openalex-snapshot

Unstructured Hardness to Average-Case Randomness

inferred← citeshttps://doi.org/10.1109/focs54457.2022.00058openalex-snapshot

Hardness Self-Amplification from Feasible Hard-Core Sets

inferred← citeshttps://doi.org/10.1109/focs57990.2023.00061openalex-snapshot

Certified Hardness vs. Randomness for Log-Space

inferred← citeshttps://doi.org/10.1109/focs57990.2023.00062openalex-snapshot

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

inferred← citeshttps://doi.org/10.1109/focs57990.2023.00074openalex-snapshot

Polynomial-Time Pseudodeterministic Construction of Primes

inferred← citeshttps://doi.org/10.1109/focs61266.2024.00095openalex-snapshot

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness

inferred← citeshttps://doi.org/10.1109/focs61266.2024.00113openalex-snapshot

An Improved Line-Point Low-Degree Test*

inferred← citeshttps://doi.org/10.1109/focs61266.2024.00140openalex-snapshot

On the Complexity of Avoiding Heavy Elements

inferred← citeshttps://doi.org/10.1109/isit.2006.261690openalex-snapshot

List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity

inferred← citeshttps://doi.org/10.1109/isit45174.2021.9518249openalex-snapshot

Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions

inferred← citeshttps://doi.org/10.1109/isit54713.2023.10206655openalex-snapshot

Computationally Relaxed Locally Decodable Codes, Revisited

inferred← citeshttps://doi.org/10.1109/itw.2003.1216683openalex-snapshot

On recursive decoding with sublinear complexity for Reed-Muller codes

inferred← citeshttps://doi.org/10.1109/itw.2006.1633776openalex-snapshot

List Decoding in Average-Case Complexity and Pseudorandomness

inferred← citeshttps://doi.org/10.1109/itw.2012.6404635openalex-snapshot

Characterizing pseudoentropy

inferred← citeshttps://doi.org/10.1109/itw46852.2021.9457613openalex-snapshot

Decoding of Lifted Affine-Invariant Codes

inferred← citeshttps://doi.org/10.1109/sfcs.2000.892063openalex-snapshot

Extracting randomness from samplable distributions

inferred← citeshttps://doi.org/10.1109/sfcs.2001.959879openalex-snapshot

Coding theory: Tutorial & survey

inferred← citeshttps://doi.org/10.1109/sfcs.2001.959941openalex-snapshot

Simple extractors for all min-entropies and a new pseudo-random generator

inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181992openalex-snapshot

Power from random strings

inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238187openalex-snapshot

List-decoding using the XOR lemma

inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238205openalex-snapshot

On Worst‐Case to Average‐Case Reductions for NP Problems

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814579openalex-snapshot

Derandomizing Arthur-Merlin games using hitting sets

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814590openalex-snapshot

Near-optimal conversion of hardness into pseudo-randomness

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814619openalex-snapshot

Hardness of approximating Σ/sub 2//sup p/ minimization problems

inferred← citeshttps://doi.org/10.1109/snpd-sawn.2005.3openalex-snapshot

A List-Decodable Code with Local Encoding and Decoding

inferred← citeshttps://doi.org/10.1109/tit.2004.825043openalex-snapshot

List Decoding of $q$ -ary Reed–Muller Codes

inferred← citeshttps://doi.org/10.1109/tit.2004.838377openalex-snapshot

Extractor Codes

inferred← citeshttps://doi.org/10.1109/tit.2008.928988openalex-snapshot

On the Complexity of Hardness Amplification

inferred← citeshttps://doi.org/10.1109/tit.2010.2095193openalex-snapshot

Soft Decoding, Dual BCH Codes, and Better List-Decodable $\varepsilon$-Biased Codes

inferred← citeshttps://doi.org/10.1109/tit.2012.2184841openalex-snapshot

Weight Distribution and List-Decoding Size of Reed–Muller Codes

inferred← citeshttps://doi.org/10.1109/tit.2016.2538766openalex-snapshot

List-Decoding Algorithms for Lifted Codes

inferred← citeshttps://doi.org/10.1109/tit.2018.2809788openalex-snapshot

Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound

inferred← citeshttps://doi.org/10.1109/tit.2018.2822686openalex-snapshot

The List Decoding Radius for Reed–Muller Codes Over Small Fields

inferred← citeshttps://doi.org/10.1109/tit.2020.2977319openalex-snapshot

On the Weights of General MDS Codes

inferred← citeshttps://doi.org/10.1109/tit.2020.3023962openalex-snapshot

On List Recovery of High-Rate Tensor Codes

inferred← citeshttps://doi.org/10.1109/tit.2021.3131992openalex-snapshot

Efficient List-Decoding With Constant Alphabet and List Sizes

inferred← citeshttps://doi.org/10.1109/tit.2022.3214372openalex-snapshot

Bias vs Structure of Polynomials in Large Fields, and Applications in Information Theory

inferred← citeshttps://doi.org/10.1109/tit.2022.3222877openalex-snapshot

List-Decoding and List-Recovery of Reed–Solomon Codes Beyond the Johnson Radius for Every Rate

inferred← citeshttps://doi.org/10.1109/tit.2023.3304614openalex-snapshot

Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

inferred← citeshttps://doi.org/10.1109/tit.2024.3357703openalex-snapshot

Threshold Rates of Code Ensembles: Linear Is Best

inferred← citeshttps://doi.org/10.1109/tit.2024.3430842openalex-snapshot

Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

inferred← citeshttps://doi.org/10.1137/050628994openalex-snapshot

Power from Random Strings

inferred← citeshttps://doi.org/10.1137/050640941openalex-snapshot

Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates

inferred← citeshttps://doi.org/10.1137/070683994openalex-snapshot

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification

inferred← citeshttps://doi.org/10.1137/070698348openalex-snapshot

Low-End Uniform Hardness versus Randomness Tradeoffs for AM

inferred← citeshttps://doi.org/10.1137/070702680openalex-snapshot

Circuit Lower Bounds for Merlin–Arthur Classes

inferred← citeshttps://doi.org/10.1137/070705258openalex-snapshot

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

inferred← citeshttps://doi.org/10.1137/080728561openalex-snapshot

Local Monotonicity Reconstruction

inferred← citeshttps://doi.org/10.1137/080734030openalex-snapshot

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot

Hardness Amplification Proofs Require Majority

inferred← citeshttps://doi.org/10.1137/080735850openalex-snapshot

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

inferred← citeshttps://doi.org/10.1137/09076787xopenalex-snapshot

Short Seed Extractors against Quantum Storage

inferred← citeshttps://doi.org/10.1137/090778274openalex-snapshot

List Decoding Tensor Products and Interleaved Codes

inferred← citeshttps://doi.org/10.1137/1.9781611973105.31openalex-snapshot

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

inferred← citeshttps://doi.org/10.1137/1.9781611975031.43openalex-snapshot

Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius

inferred← citeshttps://doi.org/10.1137/1.9781611975482.61openalex-snapshot

XOR Codes and Sparse Learning Parity with Noise

inferred← citeshttps://doi.org/10.1137/1.9781611975994.179openalex-snapshot

Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs

showing the first 200 of 342 · page through all 342

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.