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?
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.