Superpolynomial lower bounds for monotone span programs
From MaRDI portal
Publication:1977413
DOI10.1007/s004930050058zbMath0990.68077OpenAlexW2571456248MaRDI QIDQ1977413
László Babai, Avi Wigderson, Anna Gál
Publication date: 14 May 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050058
Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Quadratic secret sharing and conditional disclosure of secrets, Secret-sharing schemes for very dense graphs, Optimal linear secret sharing schemes for graph access structures on six participants, Threshold Secret Sharing Requires a Linear Size Alphabet, Towards breaking the exponential barrier for general secret sharing, Improving the linear programming technique in the search for lower bounds in secret sharing, Binary Covering Arrays and Existentially Closed Graphs, Local bounds for the optimal information ratio of secret sharing schemes, On reducibility and symmetry of disjoint NP pairs., Acyclicity programming for sigma-protocols, On Linear Secret Sharing for Connectivity in Directed Graphs, On the number of zero-patterns of a sequence of polynomials, Secret-Sharing Schemes: A Survey, Existence results for cyclotomic orthomorphisms, Span-program-based quantum algorithm for evaluating formulas, Random constructions and density results, A note on monotone complexity and the rank of matrices, On abelian and homomorphic secret sharing schemes, On pseudorandom subsets in finite fields. I: Measure of pseudorandomness and support of Boolean functions, Adventures in monotone complexity and TFNP, Secret Sharing Schemes for Dense Forbidden Graphs, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Unnamed Item, Unnamed Item, Secret sharing schemes for ports of matroids of rank 3
