ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Can one efficiently reduce the number of bits in the coefficients of an n-variable linear threshold function from, say, n100 bits down to n2 bits? Can one find PC/SA/SOS degree lower bounds for graph iso- morphism formulas ISO(G, H) that do not come from CFI graphs or their small variants? How strong is a deductive proof system in which lines are represented by DNNF (Decomposable Negation Normal Form) formulas? The report passage is retained verbatim as the relevant context for this extracted problem.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.