Zobrazeno 1 - 10
of 79
pro vyhledávání: '"Chattopadhyay, Arkadev"'
Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret [Ann. Pure Ap
Externí odkaz:
http://arxiv.org/abs/2402.04364
We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a
Externí odkaz:
http://arxiv.org/abs/2211.17214
We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having $n$ variables and defined over cons
Externí odkaz:
http://arxiv.org/abs/2109.06941
Autor:
Chakraborty, Sourav, Chattopadhyay, Arkadev, Høyer, Peter, Mande, Nikhil S., Paraashar, Manaswi, de Wolf, Ronald
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes t
Externí odkaz:
http://arxiv.org/abs/2012.05233
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$
Externí odkaz:
http://arxiv.org/abs/2009.02717
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \
Externí odkaz:
http://arxiv.org/abs/1909.10428
Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to\{0,1\}$ to the communication complexity of the composed function $f \circ g^{n}$, for some "gadget" $g:\{0,1\}^{b}\times\{0,1\}^{b}\to\{0,1\}$. Such theore
Externí odkaz:
http://arxiv.org/abs/1904.13056
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list com
Externí odkaz:
http://arxiv.org/abs/1901.05911
Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the s
Externí odkaz:
http://arxiv.org/abs/1705.02397
We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming satisfy this property, and as a corollary we obtain deterministic simul
Externí odkaz:
http://arxiv.org/abs/1704.06807