More Like this

1. Leakage-Resilient Hardness vs Randomness

   https://doi.org/10.4230/LIPIcs.CCC.2023.32  

   Liu, Yanyi; Pass, Rafael (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated "hardness v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84), Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness assumptions under which e.g., prBPP = prP (so-called "high-end derandomization), or prBPP ⊆ prSUBEXP (so-called "low-end derandomization), and more generally, under which prBPP ⊆ prDTIME(𝒞) where 𝒞 is a "nice" class (closed under composition with a polynomial), but these hardness assumptions are not known to also be necessary for such derandomization. In this work, following the recent work by Chen and Tell (FOCS’21) that considers "almost-all-input" hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider "almost-all-input" leakage-resilient hardness of a function f - that is, hardness of computing f(x) even given, say, √|x| bits of leakage of f(x). We show that leakage-resilient hardness characterizes derandomization of prBPP (i.e., gives a both necessary and sufficient condition for derandomization), both in the high-end and in the low-end setting. In more detail, we show that there exists a constant c such that for every function T, the following are equivalent: - prBPP ⊆ prDTIME(poly(T(poly(n)))); - Existence of a poly(T(poly(n)))-time computable function f :{0,1}ⁿ → {0,1}ⁿ that is almost-all-input leakage-resilient hard with respect to n^c-time probabilistic algorithms. As far as we know, this is the first assumption that characterizes derandomization in both the low-end and the high-end regime. Additionally, our characterization naturally extends also to derandomization of prMA, and also to average-case derandomization, by appropriately weakening the requirements on the function f. In particular, for the case of average-case (a.k.a. "effective") derandomization, we no longer require the function to be almost-all-input hard, but simply satisfy the more standard notion of average-case leakage-resilient hardness (w.r.t., every samplable distribution), whereas for derandomization of prMA, we instead consider leakage-resilience for relations. 

   more » « less
2. Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

   Doron, Dean; Pyne, Ted; Tell, Roei (June 2024, 56th Annual ACM Symposium on Theory of Computing (STOC 2024))

   We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. We prove one such result for showing that BPL=L “on average”, and another similar result for showing that BPSPACE[O(n)]=DSPACE[O(n)]. Next, we significantly improve the main results of prior works on hardness-vs.-randomness for logspace. As one of our results, we relax the assumptions needed for derandomization with minimal memory footprint (i.e., showing BPSPACE[S]⊆ DSPACE[c · S] for a small constant c), by completely eliminating a cryptographic assumption that was needed in prior work. A key contribution underlying all of our results is non-black-box use of the descriptions of space-bounded Turing machines, when proving hardness-to-randomness results. That is, the crucial point allowing us to prove our results is that we use properties that are specific to space-bounded machines. 

   more » « less
3. Deep Network With Approximation Error Being Reciprocal of Width to Power of Square Root of Depth

   https://doi.org/10.1162/neco_a_01364  

   Shen, Zuowei; Yang, Haizhao; Zhang, Shijun (January 2021, Neural Computation)

   null (Ed.)

   A new network with super-approximation power is introduced. This network is built with Floor (⌊x⌋) or ReLU (max{0,x}) activation function in each neuron; hence, we call such networks Floor-ReLU networks. For any hyperparameters N∈N+ and L∈N+, we show that Floor-ReLU networks with width max{d,5N+13} and depth 64dL+3 can uniformly approximate a Hölder function f on [0,1]d with an approximation error 3λdα/2N-αL, where α∈(0,1] and λ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function f on [0,1]d with a modulus of continuity ωf(·), the constructive approximation rate is ωf(dN-L)+2ωf(d)N-L. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ωf(r) as r→0 is moderate (e.g., ωf(r)≲rα for Hölder continuous functions), since the major term to be considered in our approximation rate is essentially d times a function of N and L independent of d within the modulus of continuity. 

   more » « less
4. Unitary signings and induced subgraphs of Cayley graphs of $$\mathbb{Z}_2^{n}$$

   https://doi.org/10.19086/aic.17912  

   Alon, Noga; Zheng, Kai (November 2020, Advances in Combinatorics)

   null (Ed.)

   Boolean functions play an important role in many different areas of computer science. The _local sensitivity_ of a Boolean function $$f:\{0,1\}^n\to \{0,1\}$$ on an input $$x\in\{0,1\}^n$$ is the number of coordinates whose flip changes the value of $f(x)$, i.e., the number of i's such that $$f(x)\not=f(x+e_i)$$, where $$e_i$$ is the $$i$$-th unit vector. The _sensitivity_ of a Boolean function is its maximum local sensitivity. In other words, the sensitivity measures the robustness of a Boolean function with respect to a perturbation of its input. Another notion that measures the robustness is block sensitivity. The _local block sensitivity_ of a Boolean function $$f:\{0,1\}^n\to \{0,1\}$ on an input $$x\in\{0,1\}^n$$ is the number of disjoint subsets $$I$$ of $$\{1,..,n\}$$ such that flipping the coordinates indexed by $$I$$ changes the value of $f(x)$$, and the _block sensitivity_ of $$f$$ is its maximum local block sensitivity. Since the local block sensitivity is at least the local sensitivity for any input $$x$$, the block sensitivity of $$f$$ is at least the sensitivity of $$f$$.The next example demonstrates that the block sensitivity of a Boolean function is not linearly bounded by its sensitivity. Fix an integer $$k\ge 2$$ and define a Boolean function $$f:\{0,1\}^{2k^2}\to\{0,1\}$$ as follows: the coordinates of $$x\in\{0,1\}^{2k^2}$$ are split into $$k$$ blocks of size $2k$ each and $f(x)=1$ if and only if at least one of the blocks contains exactly two entries equal to one and these entries are consecutive. While the sensitivity of the function $$f$$ is $2k$, its block sensitivity is $k^2$. The Sensitivity Conjecture, made by Nisan and Szegedy in 1992, asserts that the block sensitivity of a Boolean function is polynomially bounded by its sensivity. The example above shows that the degree of such a polynomial must be at least two.The Sensitivity Conjecture has been recently proven by Huang in [Annals of Mathematics 190 (2019), 949-955](https://doi.org/10.4007/annals.2019.190.3.6). He proved the following combinatorial statement that implies the conjecture (with the degree of the polynomial equal to four): any subset of more than half of the vertices of the $$n$$-dimensional cube $$\{0,1\}^n$$ induces a subgraph that contains a vertex with degree at least $$\sqrt{n}$$. The present article extends this result as follows: every Cayley graph with the vertex set $$\{0,1\}^n$$ and any generating set of size $$d$$ (the vertex set is viewed as a vector space over the binary field) satisfies that any subset of more than half of its vertices induces a subgraph that contains a vertex of degree at least $$\sqrt{d}$$. In particular, when the generating set consists of the $$n$$ unit vectors, the Cayley graph is the $$n$$-dimensional hypercube. 

   more » « less
5. The query complexity of certification

   https://doi.org/10.1145/3519935.3519993  

   Blanc, G.; Koch, C.; Lange, J.; Tan, L. (January 2022, 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 22))

   We study the problem of certification: given queries to a function f : {0,1}n → {0,1} with certificate complexity ≤ k and an input x⋆, output a size-k certificate for f’s value on x⋆. For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O(k8 logn) queries, which comes close to matching the information-theoretic lower bound of Ω(k logn). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in-k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f. These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve. 

   more » « less