Lifting Nullstellensatz to monotone span programs over any field

DOI10.1145/3188745.3188914zbMath1428.68152OpenAlexW2809402609MaRDI QIDQ5230374

Toniann Pitassi, Robert Robere

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188914

zbMATH Keywords

circuit complexityswitching networksmonotone complexityspan programsformulascomparator circuitsrank method

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Authentication, digital signatures and secret sharing (94A62) Computational methods for problems pertaining to field theory (12-08) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Upslices, downslices, and secret-sharing with complexity of \(1.5^n\) ⋮ Quadratic secret sharing and conditional disclosure of secrets ⋮ Improving the linear programming technique in the search for lower bounds in secret sharing ⋮ Acyclicity programming for sigma-protocols ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ On abelian and homomorphic secret sharing schemes ⋮ Adventures in monotone complexity and TFNP ⋮ Lifting Theorems for Equality ⋮ Unnamed Item ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets