Math 2.0

Resources / preprint

Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds ZZER8ZBSCR

URIm2://res/ZZER8ZBSCR
Kindpreprint
CreatorsXin Li, Yan Zhong
Date2026-10-01
MSC05-XX
Subjectsarxiv cs.CC, arxiv math.AG, arxiv math.CO
Scopein

Expressions

e1: version, preprint

Languageen
Date2026-10-01
IdsarXiv 2610.02407

Items in this resource

The mentions of the inventory that name this resource. Each name links to the card of its inventory row.

ItemKindWhereSource
Strong correlation breaker with advicedefinitiondefinition 2.14arxiv
Expected Queries and Query Tailsstatementproposition 5.11arxiv
Prescribed output length and errorstatementproposition 5.8arxiv
Correlation breaker with advicestatementtheorem 2.15arxiv
Tagged matching boundstatementtheorem 6.13arxiv
A linear seeded extractor with a tunable seed lengthstatementtheorem 2.13arxiv
Common constant spacesstatementlemma 5.3arxiv
Affine non-malleability implies average-case hardnessstatementtheorem 1.6arxiv
Assemblystatementlemma B.11arxiv
Fourier correlations between the two outputsstatementlemma 3.11arxiv
Decorrelation across disjoint affine sectionsdefinitiondefinition 4.3arxiv
Tagged liftingstatementcorollary 6.14arxiv
Partial condensationstatementlemma 6.23arxiv
Constant row weightstatementlemma 6.25arxiv
Logarithmic overhead from sumset extractorsstatementtheorem 5.25arxiv
Conditioning on the displacementstatementlemma 4.5arxiv
Prescribed joint output patternsstatementlemma 6.16arxiv
Non-Oblivious Local Depthstatementtheorem 1.10arxiv
Direct overlapping size--depth tradeoffstatementtheorem 1.11arxiv
Non-malleable affine extractors for sublinear entropystatementtheorem 1.3arxiv
Explicit bounded-depth lower boundsstatementcorollary 6.11arxiv
Selecting a good blockstatementlemma 3.10arxiv
Non-malleable affine extractordefinitiondefinition 1.1arxiv
An Affine Space Through a Prescribed Common Zerostatementlemma 5.16arxiv
Rank certificatedefinitiondefinition B.1arxiv
Independence mergingstatementlemma 2.3arxiv
List Prediction with Independent Uniform Auxiliary Inputsstatementtheorem A.6arxiv
Tseitin legal assignmentsstatementlemma 6.10arxiv
8WBT40CMN5statementcorollary 6.22arxiv
Universal rank certificatestatementtheorem B.6arxiv
Average-case boundsstatementproposition 5.2arxiv
Directional derivative biasdefinitiondefinition 4.2arxiv
Affine conditioningstatementlemma 2.6arxiv
Non-malleable affine extractorsstatementcorollary 5.29arxiv
Generic exact boundsstatementtheorem 5.4arxiv
Ingredients for the initial seedstatementlemma 3.6arxiv
Depth From Affine Dispersionstatementtheorem 5.17arxiv
Disjoint majority restrictionsstatementlemma 6.18arxiv
An asymmetric separated partitionstatementlemma 5.26arxiv
Advice generatorstatementlemma 3.4arxiv
The affine-state invariantstatementlemma 6.7arxiv
Non-malleability under translations and low-degree correlationstatementtheorem 5.12arxiv
Ordered accumulatorstatementlemma 6.27arxiv
List predictionstatementtheorem A.5arxiv
Affine non-malleability implies weakly read-once hardnessstatementtheorem 4.11arxiv
Correlation with quadratic polynomialsstatementlemma 5.1arxiv
Lower bound on clause rankstatementcorollary 6.8arxiv
A cut of bounded size in a full programstatementlemma 4.6arxiv
Non-oblivious degree-$2$ depth upper boundstatementproposition 5.7arxiv
Growing Query Degreestatementcorollary 5.15arxiv
D1MT156V4Cstatementlemma B.15arxiv
Simultaneous selectionstatementlemma B.10arxiv
Bounded-degree affine extractorsstatementtheorem 2.16arxiv
Weakly read-once linear branching programdefinitiondefinition 4.1arxiv
DWRE6J6KSVstatementtheorem 3.13arxiv
Separated leavesstatementproposition 5.23arxiv
Directional hardness with independent uniform auxiliary variablesstatementtheorem A.2arxiv
Normalization and coordinate enlargementstatementlemma B.7arxiv
A cut for the pure-input rankstatementlemma A.1arxiv
ERF9RSGMQQstatementlemma B.14arxiv
Alignment to original family blocksstatementlemma B.9arxiv
Overlapping size--depth transferstatementtheorem 6.19arxiv
Fixed Multiple Tamperingsstatementproposition 5.9arxiv
Higher moments with independent uniform auxiliary variablesstatementtheorem A.9arxiv
Grouped matrixstatementlemma 6.24arxiv
Deterministic Lossless Liftingstatementtheorem 6.1arxiv
Affine hardness with independent uniform auxiliary variablesstatementtheorem A.4arxiv
Conditioning affine sourcesstatementlemma 2.5arxiv
Non-malleable affine extractors for jointly affine inputsstatementtheorem 3.14arxiv
Boolean projection roundingstatementlemma B.4arxiv
Monotone closurestatementlemma 6.6arxiv
Affine sections from future transcriptsstatementlemma 4.7arxiv
Intersecting projected sectionsstatementlemma A.3arxiv
Combining the outputsstatementtheorem 3.9arxiv
Repair with an additive defect boundstatementlemma B.8arxiv
HDH1C3JBHYstatementtheorem 3.17arxiv
Affine fibers and sectionsdefinitiondefinition 2.4arxiv
Directional derivative bounds on separated leavesstatementlemma 5.27arxiv
Lower bounds on extractor errorstatementlemma 5.5arxiv
HWW8Q37F2Dstatementcorollary 3.12arxiv
Deterministic Simultaneous Surjectivitystatementtheorem 6.2arxiv
A restricted gadgetstatementlemma 6.3arxiv
Local hardness from directional derivative boundsstatementtheorem 5.28arxiv
Output probabilities on safe affine spacesstatementlemma 6.5arxiv
Linear seeded extractorsstatementtheorem 2.12arxiv
$t$-Non-Malleable Affine Extractordefinitiondefinition 2.10arxiv
KHR8C3QAS8statementlemma 2.1arxiv
Non-Oblivious Depth at Fixed Entropy Ratestatementtheorem 1.9arxiv
Higher moments for list predictionstatementtheorem A.8arxiv
Strong seeded extractordefinitiondefinition 2.2arxiv
Quadratic size--depth tradeoffstatementtheorem 1.12arxiv
Signed completion to the entropy thresholdstatementlemma 5.22arxiv
Higher momentsstatementtheorem A.7arxiv
N5833TA5VDstatementlemma B.13arxiv
Correlation Transferstatementproposition 5.10arxiv
Moments with a linear characterstatementlemma 6.4arxiv
NTN9FZ3S43statementcorollary 3.19arxiv
P7QQW5BK2Vstatementlemma B.12arxiv
Equivalent Jointly Affine Formulationstatementlemma 2.11arxiv
Directional affine extractordefinitiondefinition 1.4arxiv
Affine non-malleability implies section decorrelationstatementlemma 4.4arxiv
Properties of one iterationstatementproposition 3.7arxiv
PQVQJSGHF0statementcorollary 5.20arxiv
Q4EQ6B2D0Jstatementtheorem 6.21arxiv
Directional affine extractors imply weakly read-once hardnessstatementtheorem 4.10arxiv
Growing an Affine Rowstatementlemma 3.5arxiv
Matching Bounds at Fixed Entropy Ratestatementcorollary 5.13arxiv
Counting displacementsstatementlemma A.10arxiv
Non-oblivious and oblivious degree-$2$ decision-tree depthstatementtheorem 1.8arxiv
A fixed number of affine tamperingsstatementcorollary 3.15arxiv
Correlation boundstatementtheorem 4.8arxiv
Separating the path supportsstatementlemma 5.24arxiv
Common bad-seed setstatementlemma 2.9arxiv
Legal partial assignmentsdefinitiondefinition 2.17arxiv
Conditioning on several outputsstatementlemma 3.16arxiv
Block lengthstatementlemma 6.17arxiv
V194YME2QMstatementlemma 2.8arxiv
Exponential average-case hardnessstatementcorollary 1.7arxiv
Exact uniformity on affine fibersstatementcorollary 3.2arxiv
Partitioning according to equalities among tampered inputsstatementlemma 3.18arxiv
Cluster product boundstatementtheorem B.2arxiv
Directional overlapping-gadget liftingstatementtheorem 6.9arxiv
Sublinear Entropy at Fixed Degreestatementcorollary 5.14arxiv
Directional affine extractors imply average-case hardnessstatementtheorem 1.5arxiv
Rectangular block completionstatementlemma B.5arxiv
Correlation with bounded-degree polynomial phasesstatementlemma 3.8arxiv
Rectangle depth boundstatementtheorem 5.18arxiv
Prescribed Output and Errorstatementcorollary 3.20arxiv
WK90YNQB5Cstatementlemma 6.26arxiv
Small localitiesstatementproposition 5.19arxiv
XQGQ53YRVXstatementcorollary 6.20arxiv
Cubic trace on affine sectionsstatementlemma A.11arxiv
YVSW5PB8QCstatementtheorem B.16arxiv
The cubic trace functionstatementcorollary 4.12arxiv
Non-malleable affine extractors for linear entropystatementtheorem 1.2arxiv
Rank capacities for two conditioning spacesstatementlemma B.3arxiv
Correlation breaking with intermediate variablesstatementlemma 3.1arxiv
A parameter consequencestatementcorollary 5.30arxiv

Catalogue records