enter search term and/or author name
Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices
Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma
Article No.: 8
We introduce the polynomial coefficient matrix and identify the maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against...
A Galois Connection for Weighted (Relational) Clones of Infinite Size
Peter Fulla, Stanislav Živný
Article No.: 9
A Galois connection between clones and relational clones on a fixed finite domain is one of the cornerstones of the so-called algebraic approach to the computational complexity of non-uniform Constraint Satisfaction Problems (CSPs). Cohen et al....
The List-Decoding Size of Fourier-Sparse Boolean Functions
Ishay Haviv, Oded Regev
Article No.: 10
A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F2n → R and parameters k and d, we prove...
We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show under some polynomial-time reductions that there are complete sets for NEXP that are not autoreducible. We...
Counting Homomorphisms to Square-Free Graphs, Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Article No.: 12
We study the problem ⊕H