Lower bounds for linear satisfiability problems

We prove an \\Omega\\Gamma n dr=2e ) lower bound for the following problem: For some fixed linear equation in r variables, given n real numbers, do any r of them satisfy the equation? Our lower bound holds in a restricted linear decision tree model, in which each decision is based on the sign of an ... View More