ProofAtlas

Analysis of Boolean functions and query complexity

Sensitivity versus Degree for Boolean Multilinear Polynomials

Collaboration beta

Find one Boolean polynomial whose number of sensitive coordinates grows faster relative to its degree than the best explicit construction currently recorded. The packet has sharply reduced one finite search, but no qualifying polynomial is known.

P(0)=0,P(ei)=1,P({0,1}18)⊆{0,1},degP≤6,19>6log6/log3
Listed inEpoch AI FrontierMath open problem
Known results and sources
A dark Boolean hypercube with eighteen coordinate rays, six translucent degree layers, and one unfilled nineteenth marker emphasizing an open construction problem.
The open task is to find an 18-variable top-one Boolean sextic that extends to 19 variables; the finite frontier is narrow but no polynomial is known.

Research problem

Exact mathematical statement

Construct a normalized 18-variable integer multilinear polynomial P with P(0)=0, P(e_i)=1, P({0,1}^{18}) contained in {0,1}, degree at most 6, and the top-one condition for the complement-extension lemma. Such a polynomial extends to a 19-variable sextic and would strictly exceed the exponent log(6)/log(3).

P(0)=0,P(ei)=1,P({0,1}18)⊆{0,1},degP≤6,19>6log6/log3P(0)=0,\quad P(e_i)=1,\quad P(\{0,1\}^{18})\subseteq\{0,1\},\quad \deg P\le 6,\qquad 19>6^{\log 6/\log 3}

Problem infographic

Problem at a glance

A three-part diagram showing an 18-coordinate Boolean cube, six degree layers, and a graph-resolved finite frontier ending in an open nineteenth-coordinate extension.
Exact finite certificates reduce one 18-variable sextic search to graph-resolved leaves; the missing object is still an explicit polynomial satisfying every Boolean and top-one constraint.

Current mathematical picture

Where work on Sensitivity versus Degree for Boolean Multilinear Polynomials stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureSource-reported closed or invalid route

The source says not to restart the symmetric quotient, top counts alone, aggregate deletion summaries alone, or a search keyed only by the 197 union count. Enumerate unlabeled eight-edge graphs G_B for universal type 0, retain structural-class data and exact deletion correlations, and emit exact certificates; then extend to the other universal types and the broad positive degree-six class.

Route status · Narrowed route
Main reductionFull Graph Lift

A retained leaf must specify (H,C,G_B) and the structural class, modulo the stated symmetry group.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeClassify the full type-0 eight-edge graph lifts without losing structural-leaf information.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Sensitivity versus Degree for Boolean Multilinear Polynomials in numbers

4.8kretained lines of mathematical investigation4,805 in the current working snapshot
Argument development
4,003 · 83%
Explored or eliminated routes
81 · 2%
Computational analysis
424 · 9%
Open obligations
156 · 3%
Definitions and setup
141 · 3%
7selected mapped statements2routes investigated4open questions4contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 15, 2026
Source recordedAug 15, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

13 selected steps

Scroll horizontally to explore the route

Working route overview for Sensitivity versus Degree for Boolean Multilinear PolynomialsA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Sensitivity versus Degree for Boolean Multilinear Polynomials — Depends on missing premiseSensitivity versus Degreefor Boolean MultilinearPolynomialsCurrent reduction — Depends on missing premiseCurrent reductionFull Graph Lift — Depends on missing premiseFull Graph LiftStructural Leaves — Depends on missing premiseStructural LeavesClosing target — Depends on missing premiseClosing targetEvidence Boundary — Depends on missing premiseEvidence BoundaryFinite Frontier — Depends on missing premiseFinite FrontierSource-reported closed or invalid route — stoppedSource-reported closed orinvalid routeSecond source-reported limitation — stoppedSecond source-reportedlimitationClassify the full type-0 eight-edge graph lifts without losing structural-leaf information. — OpenClassify the full type-0eight-edge graph liftswithout…Test rooted deletion and pair-deletion compatibility on each retained lift. — OpenTest rooted deletion andpair-deletion compatibilityon…Resolve the broad positive pure-degree-six structural class. — OpenResolve the broad positivepure-degree-six structuralclass.Normalized Target — OpenNormalized Target
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routeSource-reported closed or invalid route

The source says not to restart the symmetric quotient, top counts alone, aggregate deletion summaries alone, or a search keyed only by the 197 union count. Enumerate unlabeled eight-edge graphs G_B for universal type 0, retain structural-class data and exact deletion correlations, and emit exact certificates; then extend to the other universal types and the broad positive degree-six class.

Route status · Narrowed route
Narrowed routeSecond source-reported limitation

Reported deletion summaries are route memory, not exact source-replayed exclusion evidence; a sixteenth fixed assignment remained. Enumerate unlabeled eight-edge graphs G_B for universal type 0, retain structural-class data and exact deletion correlations, and emit exact certificates; then extend to the other universal types and the broad positive degree-six class.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks
01
Classify the full type-0 eight-edge graph lifts without losing structural-leaf information.Suggested move: Enumerate G_B up to automorphism, bind every surviving structural class, and retain exact orbit accounting and certificates.
Ready to work on
02
Test rooted deletion and pair-deletion compatibility on each retained lift.Suggested move: Encode the vertexwise correlations rather than relying on aggregate deletion summaries, and independently replay every claimed exclusion.
Ready to work on
03
Normalized Target

The active target is an 18-variable top-one Boolean sextic that would extend to 19 variables and beat log(6)/log(3).

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Resolve the broad positive pure-degree-six structural class.Suggested move: Develop candidate-adapted separation in parallel with the universal-type search while retaining all 50 source-reported surviving types.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 15, 2026
Current statusOpen problem

The explicit construction task remains open: the maintained problem page records the log(6)/log(3) construction and asks for an improvement. This is not the solved Sensitivity Conjecture.

[1]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Authoritative summaryEpoch AI lists improving the explicit log(6)/log(3) construction exponent as an open problem.[1]
  2. Peer reviewedLaplante, Naserasr, and Sunny proved the stronger bound deg(f) <= s_0(f)s_1(f), refining the general upper-bound side.[3]
  3. Peer reviewedHuang proved the Sensitivity Conjecture, establishing a polynomial relation and the quadratic degree upper-bound scale; this is distinct from optimizing explicit lower-bound separations.[2]
3 cited sources1 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusSensitivity versus Degree for Boolean Multilinear Polynomials
Related problemSensitivity Conjecture

The solved Sensitivity Conjecture gives a general polynomial upper bound; the present workspace instead seeks a better explicit sensitivity-versus-degree separation.

[2][1]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetNo current public formalization of this exact construction task was identified in the bounded official-source review.
  • Formalization targetA claimed improved polynomial would still require exact cube-value, degree, normalization, and sensitivity checking.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements4 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction3 of 73
  • lemma2 of 72
  • computational claim1 of 71
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementSensitivity versus Degree for Boolean Multilinear Polynomials
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementFinite Frontierintermediate
  • retained route statementStructural Leavesintermediate
  • retained route statementFull Graph Liftintermediate
  • retained route statementEvidence Boundaryintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureSource-reported closed or invalid routereported failure
  • Useful failureSecond source-reported limitationreported failure
  • Research targetClassify the full type-0 eight-edge graph lifts without losing structural-leaf information.open
  • Research targetTest rooted deletion and pair-deletion compatibility on each retained lift.open
  • Research targetResolve the broad positive pure-degree-six structural class.open
  • Research targetNormalized Targetopen
  • Research targetNo Candidatesuperseded
  • ComputationThe source reports exact rational certificate counts and a canonical finite frontier; ProofAtlas did not execute the current work's verification code.Source-reported result: 36,084 to 1,093 to 197 branch incidences, 51 canonical types, nine universal types; attachment execution was deliberately not performed. · reported unreproduced
  • Narrowed routeSource-reported closed or invalid routeThe source says not to restart the symmetric quotient, top counts alone, aggregate deletion summaries alone, or a search keyed only by the 197 union count. Enumerate unlabeled eight-edge graphs G_B for universal type 0, retain structural-class data and exact deletion correlations, and emit exact certificates; then extend to the other universal types and the broad positive degree-six class.
  • Narrowed routeSecond source-reported limitationReported deletion summaries are route memory, not exact source-replayed exclusion evidence; a sixteenth fixed assignment remained. Enumerate unlabeled eight-edge graphs G_B for universal type 0, retain structural-class data and exact deletion correlations, and emit exact certificates; then extend to the other universal types and the broad positive degree-six class.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeClassify the full type-0 eight-edge graph lifts without losing structural-leaf information.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointClassify the full type-0 eight-edge graph lifts without losing structural-leaf information.

Sensitivity versus Degree for Boolean Multilinear Polynomials · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Find one Boolean polynomial whose number of sensitive coordinates grows faster relative to its degree than the best explicit construction currently recorded. The current work has sharply reduced one finite search, but no qualifying polynomial is known.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 15, 2026

The mathematical context was checked on Aug 15, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Sensitivity versus Degree for Boolean Multilinear Polynomialsmaintained problem list · Epoch AI · Epoch AI · 2026 · accessed Aug 15, 2026
  2. 2
    Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecturepeer reviewed result · Hao Huang · Annals of Mathematics · 2019-10-28 · DOI 10.4007/annals.2019.190.3.6 · MR MR4024566 · accessed Aug 15, 2026
  3. 3
    Sensitivity Lower Bounds from Linear Dependenciespeer reviewed result · Sophie Laplante, Reza Naserasr, Anupa Sunny · Schloss Dagstuhl — Leibniz-Zentrum für Informatik · 2020-08-18 · DOI 10.4230/LIPIcs.MFCS.2020.62 · accessed Aug 15, 2026

Important qualifications

  • This was a bounded current-status check, not an exhaustive priority or attribution review.
  • Preprints remain labeled as preprints and were not upgraded to peer-reviewed posture.
  • Current open status was cross-checked against recent official or primary sources where available.
  • No source-package attachment was executed or rendered, and no URL copied from a submitted packet was fetched.
  • Metadata has no proof, review, acceptance, credit, publication, or deployment effect.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image