ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usWed, 12 Dec 2018 17:10:30 +0200TR18-211 | Parametric Shortest Paths in Planar Graphs |
Kshitij Gajjar,
Jaikumar Radhakrishnan
https://eccc.weizmann.ac.il/report/2018/211We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.
Gusfield (1980) and Dean (2009) showed that the number of break points for an $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + O(\alpha(n)^d)}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound arises from Davenport-Schinzel sequences.Wed, 12 Dec 2018 17:10:30 +0200https://eccc.weizmann.ac.il/report/2018/211TR18-210 | On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic |
Karthik C. S.,
Pasin Manurangsi
https://eccc.weizmann.ac.il/report/2018/210Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when $d=\omega(\log n)$ was raised as an open question in recent works (Abboud-Rubinstein-Williams [FOCS'17], Williams [SODA'18], David-Karthik-Laekhanukit [SoCG'18]).
In this paper, we show that for every $p\in\mathbb R_{\ge 1}\cup\{0\}$, under the Strong Exponential Time Hypothesis (SETH), for every $\varepsilon>0$, the following holds:
$\bullet$ No algorithm running in time $O(n^{2-\varepsilon})$ can solve the Closest Pair problem in $d=(\log n)^{\Omega_{\varepsilon}(1)}$ dimensions in the $\ell_p$-metric.
$\bullet$ There exists $\delta = \delta(\varepsilon)>0$ and $c = c(\varepsilon)\ge 1$ such that no algorithm running in time $O(n^{1.5-\varepsilon})$ can approximate Closest Pair problem to a factor of $(1+\delta)$ in $d\ge c\log n$ dimensions in the $\ell_p$-metric.
In particular, our first result is shown by establishing the computational equivalence of the bichromatic Closest Pair problem and the (monochromatic) Closest Pair problem (up to $n^{\varepsilon}$ factor in the running time) for $d=(\log n)^{\Omega_\varepsilon(1)}$ dimensions.
Additionally, under SETH, we rule out nearly-polynomial factor approximation algorithms running in subquadratic time for the (monochromatic) Maximum Inner Product problem where we are given a set of $n$ points in $n^{o(1)}$-dimensional Euclidean space and are required to find a pair of distinct points in the set that maximize the inner product.
At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on $n$ vertices with $n^{2-\varepsilon}$ edges whose vertices can be realized as points in a $(\log n)^{\Omega_\varepsilon(1)}$-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Miccancio-Sudan [IEEE Trans. Inf. Theory'03].Mon, 10 Dec 2018 02:31:47 +0200https://eccc.weizmann.ac.il/report/2018/210TR18-209 | AC0 unpredictability |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/209We prove that for every distribution $D$ on $n$ bits with Shannon
entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of
the bits $D_{i}$ can be predicted with advantage $\gamma$ by an
AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of
all the bits of $D$ except $D_{i}$. This answers a question by Meir
and Wigderson (2017) who proved a corresponding result for decision
trees.
We also show that there are distributions $D$ with entropy $\ge n-O(1)$
such that any subset of $O(n/\log n)$ bits of $D$ on can be distinguished
from uniform by a circuit of depth $2$ and size $\poly(n)$. This
separates the notions of predictability and distinguishability in
this context.
Sat, 08 Dec 2018 02:28:19 +0200https://eccc.weizmann.ac.il/report/2018/209TR18-208 | Placing Conditional Disclosure of Secrets in the Communication Complexity Universe |
Benny Applebaum,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2018/208In the *Conditional Disclosure of Secrets* (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies some predefined predicate $f$. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security.
Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate $f$ to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of $\Omega(n)$ or $\Omega(n^{1-\epsilon})$, providing an exponential improvement over previous logarithmic lower-bounds.
We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication -- a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the class AM, or even $\text{AM}\cap \text{co-AM}$ -- a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the ``civilized'' part of the communication complexity world for which explicit lower-bounds are known.Thu, 06 Dec 2018 12:32:29 +0200https://eccc.weizmann.ac.il/report/2018/208TR18-207 | On the Probabilistic Degree of OR over the Reals |
Tulasimohan Molli,
Siddharth Bhandari,
Prahladh Harsha,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2018/207We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials entirely supported on polynomials of degree at most $d$ such that for all $z \in \{0,1\}^n$, we have $Pr_{P \sim D} [P(z) = f(z) ] \geq 1- \epsilon$. It is known from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman ( Proc. 6th CCC 1991), that the $\epsilon$-error probabilistic degree of the OR function is at most $O(\log n.\log 1/\epsilon)$. Our first observation is that this can be improved to $O{\log {{n}\choose{\leq \log 1/\epsilon}}}$, which is better for small values of $\epsilon$.
In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials $P$ in the support of the distribution $D$ have the following special structure:$P = 1 - (1-L_1).(1-L_2)...(1-L_t)$, where each $L_i(x_1,..., x_n)$ is a linear form in the variables $x_1,...,x_n$, i.e., the polynomial $1-P(x_1,...,x_n)$ is a product of affine forms. We show that the $\epsilon$-error probabilistic degree of OR when restricted to polynomials of the above form is $\Omega ( \log a/\log^2 a )$ where $a = \log {{n}\choose{\leq \log 1/\epsilon}}$. Thus matching the above upper bound (up to poly-logarithmic factors). Wed, 05 Dec 2018 17:03:19 +0200https://eccc.weizmann.ac.il/report/2018/207TR18-206 | Equality Alone Does Not Simulate Randomness |
Arkadev Chattopadhyay,
Shachar Lovett,
Marc Vinyals
https://eccc.weizmann.ac.il/report/2018/206The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on $n$ bits with randomized one-sided communication complexity $O(\log n)$, but such that every deterministic protocol with access to `Equality' oracle needs $\Omega(n/\log n)$ cost to compute it. Mon, 03 Dec 2018 22:54:45 +0200https://eccc.weizmann.ac.il/report/2018/206TR18-205 | New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity |
Siddhesh Chaubal,
Anna Gal
https://eccc.weizmann.ac.il/report/2018/205Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity.
In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Some of our constructions match the current largest separation between sensitivity and block sensitivity by Ambainis and Sun. Our constructions have several novel aspects. We use more general function compositions instead of just OR-composition, and give constructions based on algebraic operations. In addition, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.Mon, 03 Dec 2018 01:54:49 +0200https://eccc.weizmann.ac.il/report/2018/205TR18-204 | Exponential Separation between Quantum Communication and Logarithm of Approximate Rank |
Makrand Sinha,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2018/204Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total
Boolean function, the sink function, that has polynomial approximate rank and
polynomial randomized communication complexity. This gives an exponential
separation between randomized communication complexity and logarithm of the
approximate rank, refuting the log-approximate-rank conjecture. We show that
even the quantum communication complexity of the sink function is polynomial,
thus also refuting the quantum log-approximate-rank conjecture.
Our lower bound is based on the fooling distribution method introduced by Rao
and Sinha (ECCC 2015) for the classical case and extended by Anshu, Touchette,
Yao and Yu (STOC 2017) for the quantum case. We also give a new proof of the
classical lower bound using the fooling distribution method. Sun, 02 Dec 2018 10:50:21 +0200https://eccc.weizmann.ac.il/report/2018/204TR18-203 | Non-Interactive Non-Malleability from Quantum Supremacy |
Yael Kalai,
Dakshita Khurana
https://eccc.weizmann.ac.il/report/2018/203We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.
First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:
- Sub-exponential hardness of factoring or discrete log.
- Quantum sub-exponential hardness of learning with errors (LWE).
Second, as our key technical contribution, we introduce a new tag amplification technique. We show how to convert any non-interactive non-malleable commitment with respect to commitment for $\epsilon \log \log n$ tags (for any constant $\epsilon>0$) into a non-interactive non-malleable commitment with respect to replacement for $2^n$ tags. This part only assumes the existence of sub-exponentially secure non-interactive witness indistinguishable (NIWI) proofs, which can be based on sub-exponential security of the decisional linear assumption.
Interestingly, for the tag amplification technique, we crucially rely on the leakage lemma due to Gentry and Wichs (STOC 2011). For the construction of non-malleable commitments for $\epsilon \log \log n$ tags, we rely on quantum supremacy. This use of quantum supremacy in classical cryptography is novel, and we believe it will have future applications. We provide one such application to two-message witness indistinguishable (WI) arguments based on the polynomial hardness of factoring and quantum polynomial hardness of LWE.Sat, 01 Dec 2018 20:29:39 +0200https://eccc.weizmann.ac.il/report/2018/203TR18-202 | A stochastic calculus approach to the oracle separation of BQP and PH |
Xinyu Wu
https://eccc.weizmann.ac.il/report/2018/202After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people
(e.g. Ryan Oâ€™Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by
stochastic calculus. In this short note, we describe such a simplification.Sat, 01 Dec 2018 14:51:33 +0200https://eccc.weizmann.ac.il/report/2018/202