Search results for "Complex."
showing 10 items of 5824 documents
On the Inner Product Predicate and a Generalization of Matching Vector Families
2018
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and mor…
Combinatorial proofs of two theorems of Lutz and Stull
2021
Recently, Lutz and Stull used methods from algorithmic information theory to prove two new Marstrand-type projection theorems, concerning subsets of Euclidean space which are not assumed to be Borel, or even analytic. One of the theorems states that if $K \subset \mathbb{R}^{n}$ is any set with equal Hausdorff and packing dimensions, then $$ \dim_{\mathrm{H}} π_{e}(K) = \min\{\dim_{\mathrm{H}} K,1\} $$ for almost every $e \in S^{n - 1}$. Here $π_{e}$ stands for orthogonal projection to $\mathrm{span}(e)$. The primary purpose of this paper is to present proofs for Lutz and Stull's projection theorems which do not refer to information theoretic concepts. Instead, they will rely on combinatori…
Unit contradiction versus unit propagation
2012
Some aspects of the result of applying unit resolution on a CNF formula can be formalized as functions with domain a set of partial truth assignments. We are interested in two ways for computing such functions, depending on whether the result is the production of the empty clause or the assignment of a variable with a given truth value. We show that these two models can compute the same functions with formulae of polynomially related sizes, and we explain how this result is related to the CNF encoding of Boolean constraints.
Adaptive learning of compressible strings
2020
Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compre…
New separation between $s(f)$ and $bs(f)$
2011
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=(2/3)s(f)^2-(1/3)s(f)$.
Adaptive Lower Bound for Testing Monotonicity on the Line
2018
In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of $\epsilon$-testing monotonicity of a function $f\colon [n]\to[r]$. All our lower bounds are for adaptive two-sided testers. * We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $\Omega(\frac{\log r}{\log \log r})$ when $\epsilon = 1/2$. No previous satisfactory lower bound in terms of $r$ was known. * We completely characterise query complexity of this probl…
Testing convexity of functions over finite domains
2019
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound $O(\frac{\log(\epsilon n)}{\epsilon})$ in the usual uniform model, and prove an $O(\frac{\log n}{\epsilon})$ upper bound in the distribution-free setting. 2. We show a tight lower bound of $\Omega(\frac{\log(\epsilon n)}{\epsilon})$ queries for testing convexity of functions $f: [n] \rightarrow \mathbb{R}$ on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adap…
Sensitivity versus Certificate Complexity of Boolean Functions
2015
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $bs(f) \leq C(f) \leq 2^{s(f)-1} s(f) - (s(f)-1)$. In this work, we give a better upper bound of $bs(f) \leq C(f) \leq \max\left(2^{s(f)-1}\left(s(f)-\frac 1 3\righ…
Probabilistic verifiers for asymmetric debates
2012
We examine the power of silent constant-space probabilistic verifiers that watch asymmetric debates (where one side is unable to see some of the messages of the other) between two deterministic provers, and try to determine who is right. We prove that probabilistic verifiers outperform their deterministic counterparts as asymmetric debate checkers. It is shown that the membership problem for every language in NSPACE(s(n)) has a 2^{s(n)}-time debate where one prover is completely blind to the other one, for polynomially bounded space constructible s(n). When partial information is allowed to be seen by the handicapped prover, the class of languages debatable in 2^{s(n)} time contains TIME(2^…
Tighter Relations Between Sensitivity and Other Complexity Measures
2014
Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004. In this work, we present new upper bounds for various complexity measures in terms of sensitivity improving the bounds provided by Kenyon and Kutin. Specifically, we show tha…