Search Results

A compression problem is defined with respect to an efficient encoding function f; given a string x, our task is to find the shortest y such that f(y) = x. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time ...

Iterated Sub-Permutation Matrix Multiplication is the problem of computing the product of k n-by-n Boolean matrices with at most a single 1 in each row and column. For all d ≤ logk, this problem is solvable by size n^O(dk1/d) monotone AC⁰ formulas of ...

The celebrated minimax principle of Yao says that for any Boolean-valued function f with finite domain, there is a distribution μ over the domain of f such that computing f to error ε against inputs from μ is just as hard as computing f to error ε on ...

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

• For every k ≥ 1, there is a monotone function in AC⁰ (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(log^k n). ...

We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class ...

Dag-like communication protocols, a generalization of the classical tree-like communication protocols, are useful objects in the realm of proof complexity (most importantly for monotone feasible interpolation) and circuit complexity. We consider three ...

The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C:0,1^n -> 0,1^l with stretch l>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and ...

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek’s theory APC₁ (2007) and of higher levels of Buss’s hierarchy S₂ⁱ (1986) has been a ...

We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our construction of subexponential circuits of depth 2 for AND helps us to classify (...

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of "incompressible strings," i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP ...

In addition to its theoretical interest, computing with circuits has found applications in many other areas such as secure multi-party computation and outsourced query processing. Yet, the exact circuit complexity of query evaluation had remained an ...

Investigating the computational resources we need for cryptography is an essential task of both theoretical and practical interests. This paper provides answers to this problem on pseudorandom functions (PRFs). We resolve the exact complexity of PRFs by ...

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich’s pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander’s neighbor function and/or of the ...

Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finit field. The expressive power of FPR properly extends that of FPC and is contained in P, but it is not ...

The orthogonality dimension of a graph G = (V, E) over a field F is the smallest integer t for which there exists an assignment of a vector u_v ∈ F^t with 〈u_v, u_v〉 ≠ 0 to every vertex v ∈ V, such that 〈u_v, u_v'〉 = 0 whenever v and v' are adjacent vertices ...

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [10]. This relaxation is still strong enough to imply P ⊈ NC¹ if proven. We also present a weaker version of this ...

Linear algebra algorithms often require some sort of iteration or recursion as is illustrated by standard algorithms for Gaussian elimination, matrix inversion, and transitive closure. A key characteristic shared by these algorithms is that they allow ...

We show unconditionally that Cook’s theory PV formalizing poly-time reasoning cannot prove, for any non-deterministic poly-time machine M defining a language L(M), that L(M) is inapproximable by co-nondeterministic circuits of sub-exponential size. In ...

We present a randomized method for computing the min-plus product (a.k.a. tropical product) of two $n \times n$ matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense $n$-node directed graphs with arbitrary ...

In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/...