ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 23 Apr 2018 23:52:21 +0300TR18-078 | Small Set Expansion in The Johnson Graph |
Subhash Khot,
Dor Minzer,
Dana Moshkovitz,
Muli Safra
https://eccc.weizmann.ac.il/report/2018/078This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if
their intersection is of size t. The Johnson graph arises often in combinatorics and theoretical computer
science: it represents a “slice” of the noisy hypercube, and it is the graph that underlies direct product
tests as well as a candidate hard unique game.
We prove that any small set of vertices in the graph either has near perfect edge expansion or is
not pseudorandom. Here “not pseudorandom” means that the set becomes denser when conditioning
on containing a small set of elements. In other words, we show that slices of the noisy hypercube –
while not small set expanders like the noisy hypercube – only have non-expanding small sets of a certain
simple structure.
This paper is related to a recent line of work establishing the 2-to-2 Theorem in PCP. The result
was motivated, in part, by [DKKMS] which hypothesized and made partial progress on similar result for the
Grassmann graph. In turn, our result for the Johnson graphs served as a crucial step towards the full
result for the Grassmann graphs completed subsequently in [KMS].Mon, 23 Apr 2018 23:52:21 +0300https://eccc.weizmann.ac.il/report/2018/078TR18-077 | Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture |
Boaz Barak,
Pravesh Kothari,
David Steurer
https://eccc.weizmann.ac.il/report/2018/077Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain ``Grassmanian agreement tester''.
In this work, we show that the hypothesis of Dinur et al follows from a conjecture we call the ``Inverse Shortcode Hypothesis'' characterizing the non-expanding sets of the degree-two shortcode graph. We also show the latter conjecture is equivalent to a characterization of the non-expanding sets in the Grassman graph, as hypothesized by a follow-up paper of Dinur et. al. (2017).
Following our work, Khot, Minzer, and Safra (2018) proved the ``Inverse Shortcode Hypothesis''. Combining their proof with our result and the reduction of Dinur et. al. (2016) completes the proof of the 2 to 2 conjecture with imperfect completeness.
Moreover, we believe that the shortcode graph provides a useful view of both the hypothesis and the reduction, and might be useful in extending it further.Mon, 23 Apr 2018 22:51:21 +0300https://eccc.weizmann.ac.il/report/2018/077TR18-076 | Torus polynomials: an algebraic approach to ACC lower bounds |
Sankeerth Rao,
Shachar Lovett,
Kaave Hosseini,
Abhishek Bhrushundi
https://eccc.weizmann.ac.il/report/2018/076We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC0 lower bounds for the majority function via our approach, we show that MAJORITY cannot be approximated by low-degree symmetric torus polynomials. We also pose several open problems related to our framework.Mon, 23 Apr 2018 21:31:25 +0300https://eccc.weizmann.ac.il/report/2018/076TR18-075 | Boolean function analysis on high-dimensional expanders |
Irit Dinur,
Yuval Filmus,
Prahladh Harsha
https://eccc.weizmann.ac.il/report/2018/075We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.
Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)| = O(n) points in comparison to ( n choose k+1) points in the (k + 1)-slice (which consists of all n-bit strings with exactly k + 1 ones).Mon, 23 Apr 2018 18:44:48 +0300https://eccc.weizmann.ac.il/report/2018/075TR18-074 | Generalized comparison trees for point-location problems |
Daniel Kane,
Shachar Lovett,
Shay Moran
https://eccc.weizmann.ac.il/report/2018/074Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from $H$; in particular, if all hyperplanes in $H$ are $k$-sparse then generalized comparisons are $2k$-sparse.
The depth of the obtained linear decision tree is polynomial in $d$ and logarithmic in $|H|$, which is comparable to previous results in the literature that use general linear queries.
This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017].
The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries.
Our analysis combines a seminal result of Forster
regarding sets in isotropic position [Forster, JCSS 2002],
the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.
Mon, 23 Apr 2018 09:28:55 +0300https://eccc.weizmann.ac.il/report/2018/074TR18-073 | NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors |
Amey Bhangale
https://eccc.weizmann.ac.il/report/2018/073We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,
(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.
In terms of NP-hardness, it improves the result of Guruswami, H{\aa}stad and Sudan ~\cite{GHS02}, combined with Moshkovitz-Raz~\cite{MR10}, by an `exponential' factor. The second result improves the result of Saket~\cite{S14} which shows $quasi$-NP-hardness of coloring a $2$-colorable $4$-uniform hypergraph with $O\left(\log^\gamma n\right)$ colors for a sufficiently small constant $1\gg\gamma>0$.
Our result is the first to show the NP-hardness of coloring a $c$-colorable $k$-uniform hypergraph with poly-logarithmically many colors, for $any$ constants $c\geq 2$ and $k\geq 3$.Sat, 21 Apr 2018 20:59:45 +0300https://eccc.weizmann.ac.il/report/2018/073TR18-072 | On the nature of the Theory of Computation (ToC) |
Avi Wigderson
https://eccc.weizmann.ac.il/report/2018/072[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].
I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, independent intellectual discipline. I discuss many aspects of the field, mainly academic but also cultural and social. The paper details of the rapid expansion of interactions ToC has with all sciences, mathematics and philosophy. I try to articulate how these connections naturally emanate from the intrinsic investigation of the notion of computation itself, and from the methodology of the field. These interactions follow the other, fundamental role that ToC played, and continues to play in the amazing developments of computer technology. I discuss some of the main intellectual goals and challenges of the field, which, together with the ubiquity of computation across human inquiry makes its study and understanding in the future at least as exciting and important as in the past.
This fantastic growth in the scope of ToC brings significant challenges regarding its internal organization, facilitating future interactions between its diverse parts and maintaining cohesion of the field around its core mission of understanding computation. Deliberate and thoughtful adaptation and growth of the field, and of the infrastructure of its community are surely required and such discussions are indeed underway. To help this discussion I review the history, culture and evolution of the field. I list what I believe are the essential characteristics which allowed ToC to so well embrace and integrate so many external influences, continuously expanding its core mission, and to create one of the greatest success stories in the history of science. I feel that preserving many of these characteristics, primarily its independence, and that educating ToC professionals (as well as other scientists, engineers, and, at appropriate levels, children and the general public too) in these achievements and challenges, are essential for a similarly spectacular future.
I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, independent intellectual discipline. I discuss many aspects of the field, mainly academic but also cultural and social. The paper details of the rapid expansion of interactions ToC has with all sciences, mathematics and philosophy. I try to articulate how these connections naturally emanate from the intrinsic investigation of the notion of computation itself, and from the methodology of the field. These interactions follow the other, fundamental role that ToC played, and continues to play in the amazing developments of computer technology. I discuss some of the main intellectual goals and challenges of the field, which, together with the ubiquity of computation across human inquiry makes its study and understanding in the future at least as exciting and important as in the past.
This fantastic growth in the scope of ToC brings significant challenges regarding its internal organization, facilitating future interactions between its diverse parts and maintaining cohesion of the field around its core mission of understanding computation. Deliberate and thoughtful adaptation and growth of the field, and of the infrastructure of its community are surely required and such discussions are indeed underway. To help this discussion I review the history, culture and evolution of the field. I list what I believe are the essential characteristics which allowed ToC to so well embrace and integrate so many external influences, continuously expanding its core mission, and to create one of the greatest success stories in the history of science. I feel that preserving many of these characteristics, primarily its independence, and that educating ToC professionals (as well as other scientists, engineers, and, at appropriate levels, children and the general public too) in these achievements and challenges, are essential for a similarly spectacular future.
Thu, 19 Apr 2018 18:12:59 +0300https://eccc.weizmann.ac.il/report/2018/072TR18-071 | Computational Two-Party Correlation |
Ronen Shaltiel,
Iftach Haitner,
Eran Omri,
Kobbi Nissim,
Jad Silbak
https://eccc.weizmann.ac.il/report/2018/071Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:
\begin{itemize}
\item We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol $\pi$, there exists an efficient \textit{simulator} such that the following holds: on input $T_\kappa$, the simulator outputs a pair $(X'_\kappa,Y'_\kappa)$ such that $(X'_\kappa,Y'_\kappa,T_\kappa)$ is (somewhat) \emph{computationally indistinguishable} from $(X_\kappa,Y_\kappa,T_\kappa)$.
\item We use these tools to prove the following \emph{dichotomy theorem}: every such protocol $\pi$ is:
\begin{itemize}
\item either \textit{uncorrelated} --- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_\kappa$, but then choose their outputs \emph{independently} from some product distribution (that is determined in poly-time from $T_\kappa$),
\item or, the protocol implies a key-agreement protocol (for infinitely many $\kappa$).
\end{itemize}
Uncorrelated protocols are completely uninteresting from a cryptographic viewpoint, as the correlation between outputs is uninteresting. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement.
\item We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function.
\item A subsequent work of \citeauthor{HaitnerMO18} uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols.
\end{itemize}
\noindent
We highlight the following two ideas regarding our technique:
\begin{itemize}
\item The simulator algorithm is obtained by a carefully designed ``competition'' between efficient algorithms attempting to forecast $((X_\kappa,Y_\kappa)|T_\kappa=t)$. The winner is used to simulate the outputs of the protocol. To the best of our knowledge, this idea has not been used before (at least in this context).
\item Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.
\end{itemize}Sun, 15 Apr 2018 12:26:33 +0300https://eccc.weizmann.ac.il/report/2018/071TR18-070 | Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More |
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2018/070We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: Here the codeword is partitioned in an unknown (but fixed) way, and then tampered by a split-state adversary. (iii) Bounded communication split-state model: In this model, the split-state adversaries are allowed to participate in a communication protocol (with bounded communication budget) to tamper the codeword. Our results are the first explicit constructions of non-malleable codes in any of these tampering models.
We derive all our non-malleable codes from explicit constructions of seedless non-malleable extractors. We believe that our results on seedless non-malleable extractors and the techniques developed are of independent interest. Using our techniques, we also give an improved extractor for an unknown interleaving of two independent sources.Sun, 15 Apr 2018 12:04:54 +0300https://eccc.weizmann.ac.il/report/2018/070TR18-069 | Constant-round interactive proof systems for AC0[2] and NC1 |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2018/069We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more relaxed notion of uniformity and offers
a better trade-off between the number of rounds and the round complexity that our proof system for NC1.
We observe that all three aforementioned systems yield constant-round doubly-efficient proof systems for the All-Pairs Shortest Paths problem.
Sat, 14 Apr 2018 21:42:53 +0300https://eccc.weizmann.ac.il/report/2018/069