Publication | Closed Access
On span programs
486
Citations
15
References
2002
Year
Unknown Venue
Mathematical ProgrammingComputational Complexity TheoryEngineeringComputational ComplexitySoftware AnalysisLinear Algebraic ModelAlgebraic ComplexitySpan ProgramsDiscrete MathematicsModel Of ComputationCombinatorial OptimizationProgramming Language TheorySpan ProgramLower BoundComputer ScienceFunctional ProgrammingTheory Of ComputingProgram AnalysisAlgebraic MethodTime ComplexityHuman-computer InteractionParallel ProgrammingSystem SoftwareInteractive Computing
A linear algebraic model of computation the span program, is introduced, and several upper and lower bounds on it are proved. These results yield applications in complexity and cryptography. The proof of the main connection, between span programs and counting branching programs, uses a variant of Razborov's general approximation method.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
| Year | Citations | |
|---|---|---|
Page 1
Page 1