Volume
LIPIcs, Volume 67
8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS)
Event
ITCS 2017, January 9-11, 2017, Berkeley, CA, USAEditor
Publication Details
- published at: 2017-11-28
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-029-3
- DBLP: db/conf/innovations/innovations2017
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 67, ITCS'17, Complete Volume
Abstract
LIPIcs, Volume 67, ITCS'17, Complete Volume
Cite as
8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@Proceedings{papadimitriou:LIPIcs.ITCS.2017,
title = {{LIPIcs, Volume 67, ITCS'17, Complete Volume}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017},
URN = {urn:nbn:de:0030-drops-82066},
doi = {10.4230/LIPIcs.ITCS.2017},
annote = {Keywords: Theory of Computation, Mathematics of Computing}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{papadimitriou:LIPIcs.ITCS.2017.0,
author = {Papadimitriou, Christos H.},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {0:i--0:x},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.0},
URN = {urn:nbn:de:0030-drops-82025},
doi = {10.4230/LIPIcs.ITCS.2017.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Separators in Region Intersection Graphs
Abstract
For undirected graphs G=(V,E) and G_0=(V_0,E_0), say that G is a region intersection graph over G_0 if there is a family of connected subsets {R_u \subseteq V_0 : u \in V} of G_0 such that {u,v} \in E \iff R_u \cap R_v \neq \emptyset.
We show if G_0 excludes the complete graph K_h as a minor for some h \geq 1, then every region intersection graph G over G_0 with m edges has a balanced separator with at most c_h \sqrt{m} nodes, where c_h is a constant depending only on h. If G additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning.
A string graph is the intersection graph of continuous arcs in the plane. String graphs are precisely region intersection graphs over planar graphs. Thus the preceding result implies that every string graph with m edges has a balanced separator of size O(\sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the O(\sqrt{m} \log m) bound of Matousek (2013).
Cite as
James R. Lee. Separators in Region Intersection Graphs. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lee:LIPIcs.ITCS.2017.1,
author = {Lee, James R.},
title = {{Separators in Region Intersection Graphs}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {1:1--1:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.1},
URN = {urn:nbn:de:0030-drops-81970},
doi = {10.4230/LIPIcs.ITCS.2017.1},
annote = {Keywords: Graph separators, planar graphs, spectral partitioning}
}
Document
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
Abstract
Given a twice continuously differentiable cost function f, we prove that the set of initial conditions so that gradient descent converges to saddle points where \nabla^2 f has at least one strictly negative eigenvalue, has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT 2016]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.
Cite as
Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{panageas_et_al:LIPIcs.ITCS.2017.2,
author = {Panageas, Ioannis and Piliouras, Georgios},
title = {{Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {2:1--2:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.2},
URN = {urn:nbn:de:0030-drops-81640},
doi = {10.4230/LIPIcs.ITCS.2017.2},
annote = {Keywords: Gradient Descent, Center-stable manifold, Saddle points, Hessian}
}
Document
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
Abstract
First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress.
We observe that the performances of gradient and mirror descent are complementary, so that faster algorithms can be designed by "linearly coupling" the two. We show how to reconstruct Nesterov's accelerated gradient methods using linear coupling, which gives a cleaner interpretation than Nesterov's original proofs. We also discuss the power of linear coupling by extending it to many other settings that Nesterov's methods cannot apply to.
Cite as
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{allenzhu_et_al:LIPIcs.ITCS.2017.3,
author = {Allen-Zhu, Zeyuan and Orecchia, Lorenzo},
title = {{Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {3:1--3:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.3},
URN = {urn:nbn:de:0030-drops-81850},
doi = {10.4230/LIPIcs.ITCS.2017.3},
annote = {Keywords: linear coupling, gradient descent, mirror descent, acceleration}
}
Document
High Dimensional Random Walks and Colorful Expansion
Abstract
Random walks on bounded degree expander graphs have numerous applications, both in theoretical and practical computational problems. A key property of these walks is that they converge rapidly to their stationary distribution.
In this work we define high order random walks: These are generalizations of random walks on graphs to high dimensional simplicial complexes, which are the high dimensional analogues of graphs. A simplicial complex of dimension d has vertices, edges, triangles, pyramids, up to d-dimensional cells. For any 0 \leq i < d, a high order random walk on dimension i moves between neighboring i-faces (e.g., edges) of the complex, where two i-faces are considered neighbors if they share a common (i+1)-face (e.g., a triangle). The case of i=0 recovers the well studied random walk on graphs.
We provide a local-to-global criterion on a complex which implies rapid convergence of all high order random walks on it. Specifically, we prove that if the 1-dimensional skeletons of all the links of a complex are spectral expanders, then for all 0 \le i < d the high order random walk on dimension i converges rapidly to its stationary distribution.
We derive our result through a new notion of high dimensional combinatorial expansion of complexes which we term colorful expansion. This notion is a natural generalization of combinatorial expansion of graphs and is strongly related to the convergence rate of the high order random walks.
We further show an explicit family of bounded degree complexes which satisfy this criterion. Specifically, we show that Ramanujan complexes meet this criterion, and thus form an explicit family of bounded degree high dimensional simplicial complexes in which all of the high order random walks converge rapidly to their stationary distribution.
Cite as
Tali Kaufman and David Mass. High Dimensional Random Walks and Colorful Expansion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 4:1-4:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kaufman_et_al:LIPIcs.ITCS.2017.4,
author = {Kaufman, Tali and Mass, David},
title = {{High Dimensional Random Walks and Colorful Expansion}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {4:1--4:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.4},
URN = {urn:nbn:de:0030-drops-81838},
doi = {10.4230/LIPIcs.ITCS.2017.4},
annote = {Keywords: High dimensional expanders, expander graphs, random walks}
}
Document
Real Stability Testing
Abstract
We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.
Cite as
Prasad Raghavendra, Nick Ryder, and Nikhil Srivastava. Real Stability Testing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{raghavendra_et_al:LIPIcs.ITCS.2017.5,
author = {Raghavendra, Prasad and Ryder, Nick and Srivastava, Nikhil},
title = {{Real Stability Testing}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {5:1--5:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.5},
URN = {urn:nbn:de:0030-drops-81965},
doi = {10.4230/LIPIcs.ITCS.2017.5},
annote = {Keywords: real stable polynomials, hyperbolic polynomials, real rootedness, moment matrix, sturm sequence}
}
Document
Very Simple and Efficient Byzantine Agreement
Abstract
We present a very simple, cryptographic, binary Byzantine-agreement protocol that, with n >= 3t+1 >= 3 players, at most t of which are malicious, halts in expected 9 rounds.
Cite as
Silvio Micali. Very Simple and Efficient Byzantine Agreement. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 6:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{micali:LIPIcs.ITCS.2017.6,
author = {Micali, Silvio},
title = {{Very Simple and Efficient Byzantine Agreement}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {6:1--6:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.6},
URN = {urn:nbn:de:0030-drops-82011},
doi = {10.4230/LIPIcs.ITCS.2017.6},
annote = {Keywords: Byzantine Agreement}
}
Document
Low-Complexity Cryptographic Hash Functions
Abstract
Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function.
The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output.
Cite as
Benny Applebaum, Naama Haramaty-Krasne, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 7:1-7:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2017.7,
author = {Applebaum, Benny and Haramaty-Krasne, Naama and Ishai, Yuval and Kushilevitz, Eyal and Vaikuntanathan, Vinod},
title = {{Low-Complexity Cryptographic Hash Functions}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {7:1--7:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.7},
URN = {urn:nbn:de:0030-drops-81901},
doi = {10.4230/LIPIcs.ITCS.2017.7},
annote = {Keywords: Cryptography, hash functions, complexity theory, coding theory}
}
Document
Hierarchical Functional Encryption
Abstract
Functional encryption provides fine-grained access control for encrypted data, allowing each user to learn only specific functions of the encrypted data. We study the notion of hierarchical functional encryption, which augments functional encryption with delegation capabilities, offering significantly more expressive access control.
We present a generic transformation that converts any general-purpose public-key functional encryption scheme into a hierarchical one without relying on any additional assumptions. This significantly refines our understanding of the power of functional encryption, showing that the existence of functional encryption is equivalent to that of its hierarchical generalization.
Instantiating our transformation with the existing functional encryption schemes yields a variety of hierarchical schemes offering various trade-offs between their delegation capabilities (i.e., the depth and width of their hierarchical structures) and underlying assumptions. When starting with a scheme secure against an unbounded number of collusions, we can support arbitrary hierarchical structures. In addition, even when starting with schemes that are secure against a bounded number of collusions (which are known to exist under rather minimal assumptions such as the existence of public-key encryption and shallow pseudorandom generators), we can support hierarchical structures of bounded depth and width.
Cite as
Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai, and Gil Segev. Hierarchical Functional Encryption. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 8:1-8:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2017.8,
author = {Brakerski, Zvika and Chandran, Nishanth and Goyal, Vipul and Jain, Aayush and Sahai, Amit and Segev, Gil},
title = {{Hierarchical Functional Encryption}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {8:1--8:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.8},
URN = {urn:nbn:de:0030-drops-81992},
doi = {10.4230/LIPIcs.ITCS.2017.8},
annote = {Keywords: Functional Encryption, Delegatable Encryption, Cryptography}
}
Document
Inferential Privacy Guarantees for Differentially Private Mechanisms
Abstract
The following is a summary of the paper "Inferential Privacy Guarantees for Differentially Private Mechanisms", presented at the Eighth Innovations in Theoretical Computer Science Conference in January 2017. The full version of the paper can be found on arXiv at the URL https://arxiv.org/abs/1603.01508.
Cite as
Arpita Ghosh and Robert Kleinberg. Inferential Privacy Guarantees for Differentially Private Mechanisms. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 9:1-9:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghosh_et_al:LIPIcs.ITCS.2017.9,
author = {Ghosh, Arpita and Kleinberg, Robert},
title = {{Inferential Privacy Guarantees for Differentially Private Mechanisms}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {9:1--9:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.9},
URN = {urn:nbn:de:0030-drops-81451},
doi = {10.4230/LIPIcs.ITCS.2017.9},
annote = {Keywords: differential privacy, statistical inference, statistical mechanics}
}
Document
Towards Human Computable Passwords
Abstract
An interesting challenge for the cryptography community is to design authentication protocols that are so simple that a human can execute them
without relying on a fully trusted computer. We propose several candidate authentication protocols for a setting in which the human user can
only receive assistance from a semi-trusted computer - a computer that stores information and performs computations correctly
but does not provide confidentiality. Our schemes use a semi-trusted computer to store and display public challenges C_i\in[n]^k.
The human user memorizes a random secret mapping \sigma:[n]\rightarrow \mathbb{Z}_d and authenticates by computing responses f(\sigma(C_i)) to
a sequence of public challenges where f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d is a function that is easy for the human to evaluate. We prove
that any statistical adversary needs to sample m=\tilde{\Omega}\paren{n^{s(f)}} challenge-response pairs to recover \sigma, for a security
parameter s(f) that depends on two key properties of f. Our lower bound generalizes recent results of Feldman et al. [Feldman'15]
who proved analogous results for the special case d=2. To obtain our results, we apply the general hypercontractivity theorem [O'Donnell'14]
to lower bound the statistical dimension of the distribution over challenge-response pairs induced by f and \sigma.
Our statistical dimension lower bounds apply to arbitrary functions f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d (not just to functions that
are easy for a human to evaluate). As an application, we propose a family of human computable password
functions f_{k_1,k_2} in which the user needs to perform 2k_1+2k_2+1 primitive operations (e.g., adding two digits or remembering a
secret value \sigma(i)), and we show that s(f) = \min{k_1+1, (k_2+1)/2}. For these schemes, we prove that forging passwords is
equivalent to recovering the secret mapping. Thus, our human computable password schemes can maintain strong security guarantees even after
an adversary has observed the user login to many different accounts.
Cite as
Jeremiah Blocki, Manuel Blum, Anupam Datta, and Santosh Vempala. Towards Human Computable Passwords. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 10:1-10:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{blocki_et_al:LIPIcs.ITCS.2017.10,
author = {Blocki, Jeremiah and Blum, Manuel and Datta, Anupam and Vempala, Santosh},
title = {{Towards Human Computable Passwords}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {10:1--10:47},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.10},
URN = {urn:nbn:de:0030-drops-81847},
doi = {10.4230/LIPIcs.ITCS.2017.10},
annote = {Keywords: Passwords, Cognitive Authentication, Human Computation, Planted Constraint Satisfaction Problem, Statistical Dimension}
}
Document
Towards Hardness of Approximation for Polynomial Time Problems
Abstract
Proving hardness of approximation is a major challenge in the field of fine-grained complexity and conditional lower bounds in P.
How well can the Longest Common Subsequence (LCS) or the Edit Distance be approximated by an algorithm that runs in near-linear time?
In this paper, we make progress towards answering these questions.
We introduce a framework that exhibits barriers for truly subquadratic and deterministic algorithms with good approximation guarantees.
Our framework highlights a novel connection between deterministic approximation algorithms for natural problems in P and circuit lower bounds.
In particular, we discover a curious connection of the following form:
if there exists a \delta>0 such that for all \eps>0 there is a deterministic (1+\eps)-approximation algorithm for LCS on two sequences of length n over an alphabet of size n^{o(1)} that runs in O(n^{2-\delta}) time, then a certain plausible hypothesis is refuted, and the class E^NP does not have non-uniform linear size Valiant Series-Parallel circuits.
Thus, designing a "truly subquadratic PTAS" for LCS is as hard as resolving an old open question in complexity theory.
Cite as
Amir Abboud and Arturs Backurs. Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 11:1-11:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{abboud_et_al:LIPIcs.ITCS.2017.11,
author = {Abboud, Amir and Backurs, Arturs},
title = {{Towards Hardness of Approximation for Polynomial Time Problems}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {11:1--11:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.11},
URN = {urn:nbn:de:0030-drops-81443},
doi = {10.4230/LIPIcs.ITCS.2017.11},
annote = {Keywords: LCS, Edit Distance, Hardness in P}
}
Document
Parameterized Property Testing of Functions
Abstract
We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to surpass the (worst-case) lower bounds, expressed in terms of the input size, for several problems. Our aim is to develop a similar level of understanding of the complexity of sublinear-time algorithms to the one that was enabled by research in parameterized complexity for classical algorithms.
Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size r of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form f:[n]\to \mathbb{R} with query complexity O(\log r), with no dependence on n. The result for monotonicity circumvents the \Omega(\log n) lower bound by Fischer (Inf. Comput., 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.
Cite as
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized Property Testing of Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{pallavoor_et_al:LIPIcs.ITCS.2017.12,
author = {Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Varma, Nithin},
title = {{Parameterized Property Testing of Functions}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {12:1--12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.12},
URN = {urn:nbn:de:0030-drops-81479},
doi = {10.4230/LIPIcs.ITCS.2017.12},
annote = {Keywords: Sublinear algorithms, property testing, parameterization, monotonicity, convexity}
}
Document
The Complexity of Problems in P Given Correlated Instances
Abstract
Instances of computational problems do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from correlations when they can be found.
[DGH, ITCS 2015] showed that significant computational gains can be made by having access to auxiliary instances which are correlated to the primary problem instance via the solution space. They demonstrate this for constraint satisfaction problems, which are NP-hard in the general worst case form.
Here, we set out to study the impact of having access to correlated instances on the complexity of polynomial time problems. Namely, for a problem P that is conjectured to require time n^c for c>0,
we ask whether access to a few instances of P that are correlated in some natural way can be used to solve P on one of them (the designated "primary instance") faster than the conjectured lower bound of n^c.
We focus our attention on a number of problems: the Longest Common Subsequence (LCS), the minimum Edit Distance between sequences, and Dynamic Time Warping Distance (DTWD) of curves, for all of which the best known algorithms achieve O(n^2/polylog(n)) runtime via dynamic programming. These problems form an interesting case in point to study, as it has been shown that a O(n^(2 - epsilon)) time algorithm for a worst-case instance would imply improved algorithms
for a host of other problems as well as disprove complexity hypotheses such as the Strong Exponential Time Hypothesis.
We show how to use access to a logarithmic number of auxiliary correlated instances, to design novel o(n^2) time algorithms for LCS, EDIT, DTWD, and more generally improved algorithms for computing any tuple-based similarity measure - a generalization which we define within on strings. For the multiple sequence alignment problem on k strings, this yields an O(nk\log n) algorithm
contrasting with classical O(n^k) dynamic programming.
Our results hold for several correlation models between the primary and the auxiliary instances. In the most general correlation model we address, we assume that the primary instance is a worst-case instance and the auxiliary instances are chosen with uniform distribution subject to the constraint that their alignments are
epsilon-correlated with the optimal alignment of the primary instance. We emphasize that optimal solutions for the auxiliary instances will not generally coincide with optimal solutions for the worst case primary instance.
We view our work as pointing out a new avenue for looking for significant improvements for sequence alignment problems and
computing similarity measures, by taking advantage of access to sequences which are correlated through natural generating processes.
In this first work we show how to take advantage of mathematically inspired simple clean models of correlation - the intriguing question, looking forward, is to find correlation models which coincide with evolutionary models and other relationships and for which our approach to multiple sequence alignment gives provable guarantees.
Cite as
Shafi Goldwasser and Dhiraj Holden. The Complexity of Problems in P Given Correlated Instances. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2017.13,
author = {Goldwasser, Shafi and Holden, Dhiraj},
title = {{The Complexity of Problems in P Given Correlated Instances}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {13:1--13:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.13},
URN = {urn:nbn:de:0030-drops-81753},
doi = {10.4230/LIPIcs.ITCS.2017.13},
annote = {Keywords: Correlated instances, Longest Common Subsequence, Fine-grained complexity}
}
Document
Multi-Clique-Width
Abstract
Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the independent set polynomial or testing c-colorability. In particular, c-colorability can be tested in time linear in n and singly exponential in c and the width k of a given multi-k-expression. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs. This gap shows up when the tree-width is basically equal to the multi-clique width as well as when the tree-width is not bounded by any function of the clique-width.
Cite as
Martin Fürer. Multi-Clique-Width. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{furer:LIPIcs.ITCS.2017.14,
author = {F\"{u}rer, Martin},
title = {{Multi-Clique-Width}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {14:1--14:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.14},
URN = {urn:nbn:de:0030-drops-81775},
doi = {10.4230/LIPIcs.ITCS.2017.14},
annote = {Keywords: clique-width, parameterized complexity, tree-width, independent set polynomial, graph coloring}
}
Document
Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
Abstract
We initiate a line of investigation into biological neural networks from an algorithmic perspective. We develop a simplified but biologically plausible model for distributed computation in stochastic spiking neural networks and study tradeoffs between computation time and network complexity in this model. Our aim is to abstract real neural networks in a way that, while not capturing all interesting features, preserves high-level behavior and allows us to make biologically relevant conclusions.
In this paper, we focus on the important 'winner-take-all' (WTA) problem, which is analogous to a neural leader election unit: a network consisting of $n$ input neurons and n corresponding output neurons must converge to a state in which a single output corresponding to a firing input (the 'winner') fires, while all other outputs remain silent. Neural circuits for WTA rely on inhibitory neurons, which suppress the activity of competing outputs and drive the network towards a converged state with a single firing winner. We attempt to understand how the number of inhibitors used affects network convergence time.
We show that it is possible to significantly outperform naive WTA constructions through a more refined use of inhibition, solving the problem in O(\theta) rounds in expectation with just O(\log^{1/\theta} n) inhibitors for any \theta. An alternative construction gives convergence in O(\log^{1/\theta} n) rounds with O(\theta) inhibitors. We complement these upper bounds with our main technical contribution, a nearly matching lower bound for networks using \ge \log \log n inhibitors. Our lower bound uses familiar indistinguishability and locality arguments from distributed computing theory applied to the neural setting. It lets us derive a number of interesting conclusions about the structure of any network solving WTA with good probability, and the use of randomness and inhibition within such a network.
Cite as
Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 15:1-15:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lynch_et_al:LIPIcs.ITCS.2017.15,
author = {Lynch, Nancy and Musco, Cameron and Parter, Merav},
title = {{Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {15:1--15:44},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.15},
URN = {urn:nbn:de:0030-drops-81952},
doi = {10.4230/LIPIcs.ITCS.2017.15},
annote = {Keywords: biological distributed algorithms, neural networks, distributed lower bounds, winner-take-all networks}
}
Document
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Abstract
A new approach to understanding evolution [Valiant, JACM 2009], namely viewing it through the lens of computation,
has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted
as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [Chastain, Livnat, Papadimitriou, Vazirani, PNAS 2014]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [Wolf, Vazirani, Arkin, J. Theor. Biology], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability.
On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game.
Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.
Cite as
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. Mutation, Sexual Reproduction and Survival in Dynamic Environments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{mehta_et_al:LIPIcs.ITCS.2017.16,
author = {Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Tetali, Prasad and Vazirani, Vijay V.},
title = {{Mutation, Sexual Reproduction and Survival in Dynamic Environments}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {16:1--16:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.16},
URN = {urn:nbn:de:0030-drops-81655},
doi = {10.4230/LIPIcs.ITCS.2017.16},
annote = {Keywords: Evolution, Non-linear dynamics, Mutation}
}
Document
Self-Sustaining Iterated Learning
Abstract
An important result from psycholinguistics (Griffiths & Kalish, 2005) states that no language can be learned iteratively by rational agents in a self-sustaining manner. We show how to modify the learning process slightly in order to achieve self-sustainability. Our work is in two parts. First, we characterize iterated learnability in geometric terms and show how a slight, steady increase in the lengths of the training sessions ensures self-sustainability for any discrete language class. In the second part, we tackle the nondiscrete case and investigate self-sustainability for iterated linear regression. We discuss the implications of our findings to issues of non-equilibrium dynamics in natural algorithms.
Cite as
Bernard Chazelle and Chu Wang. Self-Sustaining Iterated Learning. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{chazelle_et_al:LIPIcs.ITCS.2017.17,
author = {Chazelle, Bernard and Wang, Chu},
title = {{Self-Sustaining Iterated Learning}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {17:1--17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.17},
URN = {urn:nbn:de:0030-drops-81711},
doi = {10.4230/LIPIcs.ITCS.2017.17},
annote = {Keywords: Iterated learning, language evolution, iterated Bayesian linear regression, non-equilibrium dynamics}
}
Document
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
Abstract
While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured that the answer is no. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap.
We prove that any undirected network with k source-sink pairs that exhibits a (1+epsilon) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G' whose gap is log(|G'|)^c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G'|), which follows from the connection between MCF and sparsest cuts.
Our construction relies on a gap-amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G'|)^c from any initial gap.
Cite as
Mark Braverman, Sumegha Garg, and Ariel Schvartzman. Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.ITCS.2017.18,
author = {Braverman, Mark and Garg, Sumegha and Schvartzman, Ariel},
title = {{Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {18:1--18:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.18},
URN = {urn:nbn:de:0030-drops-81599},
doi = {10.4230/LIPIcs.ITCS.2017.18},
annote = {Keywords: Network coding, Gap Amplification, Multicommodity flows}
}
Document
Compression in a Distributed Setting
Abstract
Motivated by an attempt to understand the formation and development of (human) language, we introduce a "distributed compression" problem. In our problem a sequence of pairs of players from a set of K players are chosen and tasked to communicate messages drawn from an unknown distribution Q.
Arguably languages are created and evolve to compress frequently occurring messages, and we focus on this aspect.
The only knowledge that players have about the distribution Q is from previously drawn samples, but these samples differ from player to player.
The only common knowledge between the players is restricted to a common prior distribution P and some constant number
of bits of information (such as a learning algorithm).
Letting T_epsilon denote the number of iterations it would take for a typical player
to obtain an epsilon-approximation to Q in total variation distance, we ask
whether T_epsilon iterations suffice to compress the messages down roughly to their
entropy and give a partial positive answer.
We show that a natural uniform algorithm can compress the communication down to an average cost per
message of O(H(Q) + log (D(P || Q)) in tilde{O}(T_epsilon) iterations
while allowing for O(epsilon)-error,
where D(. || .) denotes the KL-divergence between distributions.
For large divergences
this compares favorably with the static algorithm that ignores all samples and
compresses down to H(Q) + D(P || Q) bits, while not requiring T_epsilon * K iterations that it would take players to develop optimal but separate compressions for
each pair of players.
Along the way we introduce a "data-structural" view of the task of
communicating with a natural language and show that our natural algorithm can also be
implemented by an efficient data structure, whose storage is comparable to the storage requirements of Q and whose query complexity is comparable to the lengths of the message to be
compressed.
Our results give a plausible mathematical analogy to the mechanisms by which
human languages get created and evolve, and in particular highlights the
possibility of coordination towards a joint task (agreeing on a language)
while engaging in distributed learning.
Cite as
Badih Ghazi, Elad Haramaty, Pritish Kamath, and Madhu Sudan. Compression in a Distributed Setting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2017.19,
author = {Ghazi, Badih and Haramaty, Elad and Kamath, Pritish and Sudan, Madhu},
title = {{Compression in a Distributed Setting}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {19:1--19:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.19},
URN = {urn:nbn:de:0030-drops-81763},
doi = {10.4230/LIPIcs.ITCS.2017.19},
annote = {Keywords: Distributed Compression, Communication, Language Evolution, Isolating Hash Families}
}
Document
Outlaw Distributions and Locally Decodable Codes
Abstract
Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. Despite decades of study, the optimal trade-off between query complexity and codeword length is far from understood. In this work, we give a new characterization of LDCs using distributions over Boolean functions whose expectation is hard to approximate (in L_\infty norm) with a small number of samples. We coin the term 'outlaw distributions' for such distributions since they 'defy' the Law of Large Numbers. We show that the existence of outlaw distributions over sufficiently
'smooth' functions implies the existence of constant query LDCs and vice versa. We give several candidates for outlaw distributions over smooth functions coming from finite field incidence geometry and from hypergraph (non)expanders.
We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters.
Cite as
Jop Briët, Zeev Dvir, and Sivakanth Gopi. Outlaw Distributions and Locally Decodable Codes. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{briet_et_al:LIPIcs.ITCS.2017.20,
author = {Bri\"{e}t, Jop and Dvir, Zeev and Gopi, Sivakanth},
title = {{Outlaw Distributions and Locally Decodable Codes}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.20},
URN = {urn:nbn:de:0030-drops-81888},
doi = {10.4230/LIPIcs.ITCS.2017.20},
annote = {Keywords: Locally Decodable Code, VC-dimension, Incidence Geometry, Cayley Hypergraphs}
}
Document
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks
Abstract
Multiparty interactive coding allows a network of n parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC’94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of O(log(\Delta + 1)) for networks whose topology has a maximal degree \Delta. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send.
We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman et al. (STOC ’16) to show that if the network’s topology is a cycle, then there is a specific “cycle task” for which any coding scheme has a communication blowup of \Omega(log n). This is quite surprising since the cycle has a maximal degree of \Delta = 2, implying a coding with a constant blowup when all parties are forced to speak at all rounds.
We complement our lower bound with a matching coding scheme for the "cycle task" that has a communication blowup of \Omega(log n). This makes our lower bound for the cycle task tight.
Cite as
Ran Gelles and Yael T. Kalai. Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gelles_et_al:LIPIcs.ITCS.2017.21,
author = {Gelles, Ran and T. Kalai, Yael},
title = {{Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.21},
URN = {urn:nbn:de:0030-drops-81523},
doi = {10.4230/LIPIcs.ITCS.2017.21},
annote = {Keywords: Interactive Communication, Coding, Stochastic Noise, Communication Complexity}
}
Document
Parallel Repetition via Fortification: Analytic View and the Quantum Case
Abstract
In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings.
First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest.
An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.
Cite as
Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Parallel Repetition via Fortification: Analytic View and the Quantum Case. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 22:1-22:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bavarian_et_al:LIPIcs.ITCS.2017.22,
author = {Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry},
title = {{Parallel Repetition via Fortification: Analytic View and the Quantum Case}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {22:1--22:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.22},
URN = {urn:nbn:de:0030-drops-81670},
doi = {10.4230/LIPIcs.ITCS.2017.22},
annote = {Keywords: Parallel repetition, quantum entanglement, non-local games}
}
Document
The Classification of Reversible Bit Operations
Abstract
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits.
Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable (though with effort, one can derive from abstract considerations an algorithm that takes triply-exponential time). The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^{n}poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace."
Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Prior to this work, it was not even known that every class was finitely generated. Ruling out the possibility of additional classes, not in the list, requires involved arguments about polynomials, lattices, and Diophantine equations.
Cite as
Scott Aaronson, Daniel Grier, and Luke Schaeffer. The Classification of Reversible Bit Operations. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 23:1-23:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2017.23,
author = {Aaronson, Scott and Grier, Daniel and Schaeffer, Luke},
title = {{The Classification of Reversible Bit Operations}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {23:1--23:34},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.23},
URN = {urn:nbn:de:0030-drops-81737},
doi = {10.4230/LIPIcs.ITCS.2017.23},
annote = {Keywords: Reversible computation, Reversible gates, Circuit synthesis, Gate classification, Boolean logic, Post’s lattice}
}
Document
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication
Abstract
We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication complexity of a Boolean function in this communication model equals the logarithm of the support rank of the corresponding tensor, whereas the approximation complexity in this model equals the logarithm of the border support rank. This characterisation allows us to prove a log-rank conjecture posed by Villagra et al. for nondeterministic multiparty quantum communication with message passing.
The support rank characterization of the communication model connects quantum communication complexity intimately to the theory of asymptotic entanglement transformation and algebraic complexity theory. In this context, we introduce the graphwise equality problem. For a cycle graph, the complexity of this communication problem is closely related to the complexity of the computational problem of multiplying matrices, or more precisely, it equals the logarithm of the support rank of the iterated matrix multiplication tensor. We employ Strassen’s laser method to show that asymptotically there exist nontrivial protocols for every odd-player cyclic equality problem. We exhibit an efficient protocol for the 5-player problem for small inputs, and we show how Young flattenings yield nontrivial complexity lower bounds.
Cite as
Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam. Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{buhrman_et_al:LIPIcs.ITCS.2017.24,
author = {Buhrman, Harry and Christandl, Matthias and Zuiddam, Jeroen},
title = {{Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {24:1--24:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.24},
URN = {urn:nbn:de:0030-drops-81812},
doi = {10.4230/LIPIcs.ITCS.2017.24},
annote = {Keywords: quantum communication complexity, broadcast channel, number-in-hand, matrix multiplication, support rank}
}
Document
Quantum Codes from High-Dimensional Manifolds
Abstract
We construct toric codes on various high-dimensional manifolds. Assuming a conjecture in geometry we find families of
quantum CSS stabilizer codes on N qubits with logarithmic weight stabilizers and distance N^{1-\epsilon} for any \epsilon>0.
The conjecture is that there is a constant C>0 such that for any n-dimensional torus {\mathbb T}^n={\mathbb R}^n/\Lambda, where \Lambda is a lattice, the least volume unoriented n/2-dimensional cycle (using the Euclidean metric) representing nontrivial homology has volume at least C^n times the volume of the least volume n/2-dimensional hyperplane representing nontrivial homology; in fact, it would suffice to have this result for \Lambda an integral lattice with the cycle restricted to faces of a cubulation by unit hypercubes.
The main technical result is an estimate of Rankin invariants for certain random lattices, showing that in a certain sense they are optimal.
Additionally, we construct codes with square-root distance, logarithmic weight stabilizers, and inverse polylogarithmic soundness factor (considered as quantum locally testable codes.
We also provide an short, alternative proof that the shortest vector in the exterior power of a lattice may be non-split.
Cite as
Matthew B. Hastings. Quantum Codes from High-Dimensional Manifolds. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 25:1-25:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{hastings:LIPIcs.ITCS.2017.25,
author = {Hastings, Matthew B.},
title = {{Quantum Codes from High-Dimensional Manifolds}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {25:1--25:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.25},
URN = {urn:nbn:de:0030-drops-81708},
doi = {10.4230/LIPIcs.ITCS.2017.25},
annote = {Keywords: quantum codes, random lattices, Rankin invariants}
}
Document
Conditional Hardness for Sensitivity Problems
Abstract
In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity.
In this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required.
Finally, we give the first algorithm for the (1+\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain.
Cite as
Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 26:1-26:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{henzinger_et_al:LIPIcs.ITCS.2017.26,
author = {Henzinger, Monika and Lincoln, Andrea and Neumann, Stefan and Vassilevska Williams, Virginia},
title = {{Conditional Hardness for Sensitivity Problems}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {26:1--26:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.26},
URN = {urn:nbn:de:0030-drops-81783},
doi = {10.4230/LIPIcs.ITCS.2017.26},
annote = {Keywords: sensitivity, conditional lower bounds, data structures, dynamic graph algorithms}
}
Document
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
Abstract
Previous work of the author [Rossmann'08] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence of quantifier-rank poly(k). Quantitatively, this improves the result of [Rossmann'08], where the upper bound on quantifier-rank is a non-elementary function of k.
Cite as
Benjamin Rossman. An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{rossman:LIPIcs.ITCS.2017.27,
author = {Rossman, Benjamin},
title = {{An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.27},
URN = {urn:nbn:de:0030-drops-81435},
doi = {10.4230/LIPIcs.ITCS.2017.27},
annote = {Keywords: circuit complexity, finite model theory}
}
Document
Low-Sensitivity Functions from Unambiguous Certificates
Abstract
We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity.
Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.
Cite as
Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-Sensitivity Functions from Unambiguous Certificates. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bendavid_et_al:LIPIcs.ITCS.2017.28,
author = {Ben-David, Shalev and Hatami, Pooya and Tal, Avishay},
title = {{Low-Sensitivity Functions from Unambiguous Certificates}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {28:1--28:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.28},
URN = {urn:nbn:de:0030-drops-81869},
doi = {10.4230/LIPIcs.ITCS.2017.28},
annote = {Keywords: Boolean functions, decision tree complexity, query complexity, sensitivity conjecture}
}
Document
Testing k-Monotonicity
Abstract
A Boolean k-monotone function defined over a finite poset domain D alternates between the values 0 and 1 at most k times on any ascending chain in D. Therefore, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions.
Motivated by the recent interest in k-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of k-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are k-monotone (or are close to being k-monotone) from functions that are far from being k-monotone.
Our results include the following:
1. We demonstrate a separation between testing k-monotonicity and testing monotonicity, on the hypercube domain {0,1}^d, for k >= 3;
2. We demonstrate a separation between testing and learning on {0,1}^d, for k=\omega(\log d): testing k-monotonicity can be performed with 2^{O(\sqrt d . \log d . \log{1/\eps})} queries, while learning k-monotone functions requires 2^{\Omega(k . \sqrt d .{1/\eps})} queries (Blais et al. (RANDOM 2015)).
3. We present a tolerant test for functions f\colon[n]^d\to \{0,1\}$with complexity independent of n, which makes progress on a problem left open by Berman et al. (STOC 2014).
Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid [n]^d, and draw connections to distribution testing techniques.
Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid [n]^d, and draw connections to distribution testing techniques.
Cite as
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer. Testing k-Monotonicity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{canonne_et_al:LIPIcs.ITCS.2017.29,
author = {Canonne, Cl\'{e}ment L. and Grigorescu, Elena and Guo, Siyao and Kumar, Akash and Wimmer, Karl},
title = {{Testing k-Monotonicity}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {29:1--29:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.29},
URN = {urn:nbn:de:0030-drops-81583},
doi = {10.4230/LIPIcs.ITCS.2017.29},
annote = {Keywords: Boolean Functions, Learning, Monotonicity, Property Testing}
}
Document
What Circuit Classes Can Be Learned with Non-Trivial Savings?
Abstract
Despite decades of intensive research, efficient - or even sub-exponential time - distribution-free PAC learning algorithms are not known for many important Boolean function classes. In this work we suggest a new perspective on these learning problems, inspired by a surge of recent research in complexity theory, in which the goal is to determine whether and how much of a savings over a naive 2^n runtime can be achieved.
We establish a range of exploratory results towards this end. In more detail,
(1) We first observe that a simple approach building on known uniform-distribution learning results gives non-trivial distribution-free learning algorithms for several well-studied classes including AC0, arbitrary functions of a few linear threshold functions (LTFs), and AC0 augmented with mod_p gates.
(2) Next we present an approach, based on the method of random restrictions from circuit complexity, which can be used to obtain several distribution-free learning algorithms that do not appear to be achievable by approach (1) above. The results achieved in this way include learning algorithms with non-trivial savings for LTF-of-AC0 circuits and improved savings for learning parity-of-AC0 circuits.
(3) Finally, our third contribution is a generic technique for converting lower bounds proved using Neciporuk's method to learning algorithms with non-trivial savings. This technique, which is the most involved of our three approaches, yields distribution-free learning algorithms for a range of classes where previously even non-trivial uniform-distribution learning algorithms were not known; these classes include full-basis formulas, branching programs, span programs, etc. up to some fixed polynomial size.
Cite as
Rocco A. Servedio and Li-Yang Tan. What Circuit Classes Can Be Learned with Non-Trivial Savings?. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{servedio_et_al:LIPIcs.ITCS.2017.30,
author = {Servedio, Rocco A. and Tan, Li-Yang},
title = {{What Circuit Classes Can Be Learned with Non-Trivial Savings?}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {30:1--30:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.30},
URN = {urn:nbn:de:0030-drops-81722},
doi = {10.4230/LIPIcs.ITCS.2017.30},
annote = {Keywords: computational learning theory, circuit complexity, non-trivial savings}
}
Document
Expander Construction in VNC1
Abstract
We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson (2002), and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the "NC^1 reasoning"). As a corollary, we prove the assumption made by Jerabek (2011) that a construction of certain bipartite expander graphs can be formalized in VNC^1. This in turn implies that every proof in Gentzen's sequent calculus LK of a monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlak (2002).
Cite as
Sam Buss, Valentine Kabanets, Antonina Kolokolova, and Michal Koucky. Expander Construction in VNC1. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 31:1-31:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{buss_et_al:LIPIcs.ITCS.2017.31,
author = {Buss, Sam and Kabanets, Valentine and Kolokolova, Antonina and Koucky, Michal},
title = {{Expander Construction in VNC1}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {31:1--31:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.31},
URN = {urn:nbn:de:0030-drops-81871},
doi = {10.4230/LIPIcs.ITCS.2017.31},
annote = {Keywords: expander graphs, bounded arithmetic, alternating log time, sequent calculus, monotone propositional logic}
}
Document
Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete
Abstract
We consider the problem of clearing a system of interconnected banks that have been exposed to a shock on their assets. Eisenberg and Noe (2001) showed that when banks can only enter into simple debt contracts with each other, then a clearing vector of payments can be computed in polynomial time. In this paper, we show that the situation changes radically when banks can also enter into credit default swaps (CDSs), i.e., financial derivative contracts that depend on the default of another bank. We prove that computing an approximate solution to the clearing problem with sufficiently small constant error is PPAD-complete. To do this, we demonstrate how financial networks with debt and CDSs can encode arithmetic operations such as addition and multiplication. Our results have practical impact for network stress tests and reveal computational complexity as a new concern regarding the stability of the financial system.
Cite as
Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston. Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{schuldenzucker_et_al:LIPIcs.ITCS.2017.32,
author = {Schuldenzucker, Steffen and Seuken, Sven and Battiston, Stefano},
title = {{Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {32:1--32:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.32},
URN = {urn:nbn:de:0030-drops-81558},
doi = {10.4230/LIPIcs.ITCS.2017.32},
annote = {Keywords: Financial Networks, Credit Default Swaps, Clearing Systems, Arithmetic Circuits, PPAD}
}
Document
Testing Submodularity and Other Properties of Valuation Functions
Abstract
We show that for any constant \epsilon > 0 and p \ge 1, it is possible to distinguish functions f : \{0,1\}^n \to [0,1] that are submodular from those that are \epsilon-far from every submodular function in \ell_p distance with a constant number of queries.
More generally, we extend the testing-by-implicit-learning framework of Diakonikolas et al.(2007) to show that every property of real-valued functions that is well-approximated in \ell_2 distance by a class of k-juntas for some k = O(1) can be tested in the \ell_p-testing model with a constant number of queries. This result, combined with a recent junta theorem of Feldman and \Vondrak (2016), yields the constant-query testability of submodularity. It also yields constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions, coverage functions, and self-bounding functions.
Cite as
Eric Blais and Abhinav Bommireddi. Testing Submodularity and Other Properties of Valuation Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{blais_et_al:LIPIcs.ITCS.2017.33,
author = {Blais, Eric and Bommireddi, Abhinav},
title = {{Testing Submodularity and Other Properties of Valuation Functions}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.33},
URN = {urn:nbn:de:0030-drops-81619},
doi = {10.4230/LIPIcs.ITCS.2017.33},
annote = {Keywords: Property testing, Testing by implicit learning, Self-bounding functions}
}
Document
Algorithmic Aspects of Private Bayesian Persuasion
Abstract
We consider a multi-receivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the receivers. The sender is allowed to commit to a signaling policy where she sends a private signal to every receiver. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue.
We show that if the sender's utility is a submodular function of the set of receivers that take the desired action, then we can efficiently find a signaling policy whose revenue is at least (1-1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1-1/e) is NP-hard and, hence, the developed approximation guarantee is essentially tight. When the sender's utility is a function of the number of receivers that take the desired action (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.
Cite as
Yakov Babichenko and Siddharth Barman. Algorithmic Aspects of Private Bayesian Persuasion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{babichenko_et_al:LIPIcs.ITCS.2017.34,
author = {Babichenko, Yakov and Barman, Siddharth},
title = {{Algorithmic Aspects of Private Bayesian Persuasion}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {34:1--34:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.34},
URN = {urn:nbn:de:0030-drops-81502},
doi = {10.4230/LIPIcs.ITCS.2017.34},
annote = {Keywords: Economics of Information, Bayesian Persuasion, Signaling, Concave Closure}
}
Document
Condorcet-Consistent and Approximately Strategyproof Tournament Rules
Abstract
We consider the manipulability of tournament rules for round-robin tournaments of n competitors. Specifically, n competitors are competing for a prize, and a tournament rule r maps the result of all n(n-1)/2 pairwise matches (called a tournament, T) to a distribution over winners. Rule r is Condorcet-consistent if whenever i wins all n-1 of her matches, r selects i with probability 1.
We consider strategic manipulation of tournaments where player j might throw their match to player i in order to increase the likelihood that one of them wins the tournament. Regardless of the reason why j chooses to do this, the potential for manipulation exists as long as Pr[r(T) = i] increases by more than Pr[r(T) = j] decreases. Unfortunately, it is known that every Condorcet-consistent rule is manipulable. In this work, we address the question of how manipulable Condorcet-consistent rules must necessarily be - by trying to minimize the difference between the increase in Pr[r(T) = i] and decrease in Pr[r(T) = j] for any potential manipulating pair.
We show that every Condorcet-consistent rule is in fact 1/3-manipulable, and that selecting a winner according to a random single elimination bracket is not alpha-manipulable for any alpha > 1/3. We also show that many previously studied tournament formats are all 1/2-manipulable, and the popular class of Copeland rules (any rule that selects a player with the most wins) are all in fact 1-manipulable, the worst possible. Finally, we consider extensions to match-fixing among sets of more than two players.
Cite as
Jon Schneider, Ariel Schvartzman, and S. Matthew Weinberg. Condorcet-Consistent and Approximately Strategyproof Tournament Rules. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{schneider_et_al:LIPIcs.ITCS.2017.35,
author = {Schneider, Jon and Schvartzman, Ariel and Weinberg, S. Matthew},
title = {{Condorcet-Consistent and Approximately Strategyproof Tournament Rules}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.35},
URN = {urn:nbn:de:0030-drops-81605},
doi = {10.4230/LIPIcs.ITCS.2017.35},
annote = {Keywords: Tournament design, Non-manipulability, Condorcet-consistent, Strategyproofness}
}
Document
Nash Social Welfare, Matrix Permanent, and Stable Polynomials
Abstract
We study the problem of allocating m items to n agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective, breaking the 1/2e^(1/e) approximation factor of Cole and Gkatzelis.
Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.
Cite as
Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{anari_et_al:LIPIcs.ITCS.2017.36,
author = {Anari, Nima and Oveis Gharan, Shayan and Saberi, Amin and Singh, Mohit},
title = {{Nash Social Welfare, Matrix Permanent, and Stable Polynomials}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {36:1--36:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.36},
URN = {urn:nbn:de:0030-drops-81489},
doi = {10.4230/LIPIcs.ITCS.2017.36},
annote = {Keywords: Nash Welfare, Permanent, Matching, Stable Polynomial, Randomized Algorithm, Saddle Point}
}
Document
Multiplayer Parallel Repetition for Expanding Games
Abstract
We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games.
Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense.
We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
Cite as
Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen. Multiplayer Parallel Repetition for Expanding Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dinur_et_al:LIPIcs.ITCS.2017.37,
author = {Dinur, Irit and Harsha, Prahladh and Venkat, Rakesh and Yuen, Henry},
title = {{Multiplayer Parallel Repetition for Expanding Games}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {37:1--37:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.37},
URN = {urn:nbn:de:0030-drops-81575},
doi = {10.4230/LIPIcs.ITCS.2017.37},
annote = {Keywords: Parallel Repetition, Multi-player, Expander}
}
Document
Cumulative Space in Black-White Pebbling and Resolution
Abstract
We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling.
We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.
Cite as
Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{alwen_et_al:LIPIcs.ITCS.2017.38,
author = {Alwen, Jo\"{e}l and de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Vinyals, Marc},
title = {{Cumulative Space in Black-White Pebbling and Resolution}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {38:1--38:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.38},
URN = {urn:nbn:de:0030-drops-81918},
doi = {10.4230/LIPIcs.ITCS.2017.38},
annote = {Keywords: pebble game, pebbling, proof complexity, space, cumulative space, clause space, resolution, parallel resolution}
}
Document
A Hierarchy Theorem for Interactive Proofs of Proximity
Abstract
The number of rounds, or round complexity, used in an interactive
protocol is a fundamental resource. In this work we consider the
significance of round complexity in the context of Interactive
Proofs of Proximity (IPPs). Roughly speaking, IPPs are interactive proofs in which the verifier runs in sublinear time and is only required to reject inputs that are far from the language.
Our main result is a round hierarchy theorem for IPPs, showing
that the power of IPPs grows with the number of rounds. More
specifically, we show that there exists a gap function
g(r) = Theta(r^2) such that for every constant r \geq 1 there exists a language that (1) has a g(r)-round IPP with verification time t=t(n,r) but (2) does not have an r-round IPP with verification time t (or even verification time t'=\poly(t)).
In fact, we prove a stronger result by exhibiting a single language L such that, for every constant r \geq 1, there is an
O(r^2)-round IPP for L with t=n^{O(1/r)} verification time, whereas the verifier in any r-round IPP for L must run in time at least t^{100}. Moreover, we show an IPP for L with a poly-logarithmic number of rounds and only poly-logarithmic erification time, yielding a sub-exponential separation between the power of constant-round IPPs versus general (unbounded round) IPPs.
From our hierarchy theorem we also derive implications to standard
interactive proofs (in which the verifier can run in polynomial
time). Specifically, we show that the round reduction technique of
Babai and Moran (JCSS, 1988) is (almost) optimal among all blackbox transformations, and we show a connection to the algebrization framework of Aaronson and Wigderson (TOCT, 2009).
Cite as
Tom Gur and Ron D. Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 39:1-39:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gur_et_al:LIPIcs.ITCS.2017.39,
author = {Gur, Tom and Rothblum, Ron D.},
title = {{A Hierarchy Theorem for Interactive Proofs of Proximity}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {39:1--39:43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.39},
URN = {urn:nbn:de:0030-drops-81536},
doi = {10.4230/LIPIcs.ITCS.2017.39},
annote = {Keywords: Complexity Theory, Property Testing, Interactive Proofs}
}
Document
Cube vs. Cube Low Degree Test
Abstract
We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension 3) that intersect on a point x in F^m, and checks that the assignments to the cubes agree with each other on the point x. Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all epsilon >= poly(d)/{|F|}^{1/2}, where d is the degree. This should be compared to the previously best soundness value of epsilon >= poly(m, d)/|F|^{1/8}. Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space.
Our proof is combinatorial and direct: unlike the Raz-Safra proof, it proceeds in one shot and does not require induction on the dimension of the ambient space. The ideas in our proof come from works on direct product testing which are even simpler in the current setting thanks to the low degree.
Along the way we also prove a somewhat surprising fact about connection between different agreement tests: it does not matter if the tester chooses the cubes to intersect on points or on lines: for every given table, its success probability in either test is nearly the same.
Cite as
Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. Cube Low Degree Test. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 40:1-40:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bhangale_et_al:LIPIcs.ITCS.2017.40,
author = {Bhangale, Amey and Dinur, Irit and Livni Navon, Inbal},
title = {{Cube vs. Cube Low Degree Test}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {40:1--40:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.40},
URN = {urn:nbn:de:0030-drops-81748},
doi = {10.4230/LIPIcs.ITCS.2017.40},
annote = {Keywords: Low Degree Test, Probabilistically Checkable Proofs, Locally Testable Codes}
}
Document
On the Power of Learning from k-Wise Queries
Abstract
Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication algorithms rely on queries that provide information about a function of a single sample. (For example, a statistical query (SQ) gives an estimate of Ex_{x ~ D}[q(x)] for any choice of the query function q mapping X to the reals, where D is
an unknown data distribution over X.) Yet some data analysis algorithms rely on properties of functions that depend on multiple samples. Such algorithms would be naturally implemented using k-wise queries each of which is specified by a function q mapping X^k to the reals. Hence it is natural to ask whether algorithms using k-wise queries can solve learning problems more efficiently and by how much.
Blum, Kalai and Wasserman (2003) showed that for any weak PAC learning problem over a fixed distribution, the complexity of learning with k-wise SQs is smaller than the (unary) SQ complexity by a factor of at most 2^k. We show that for more general problems over distributions the picture is substantially richer. For every k, the complexity of distribution-independent PAC learning with k-wise queries can be exponentially larger than learning with (k+1)-wise queries. We then give two approaches for simulating a k-wise query using unary queries. The first approach exploits the structure of the
problem that needs to be solved. It generalizes and strengthens (exponentially)
the results of Blum et al.. It allows us to derive strong lower bounds for
learning DNF formulas and stochastic constraint satisfaction problems that hold
against algorithms using k-wise queries. The second approach exploits the
k-party communication complexity of the k-wise query function.
Cite as
Vitaly Feldman and Badih Ghazi. On the Power of Learning from k-Wise Queries. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 41:1-41:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{feldman_et_al:LIPIcs.ITCS.2017.41,
author = {Feldman, Vitaly and Ghazi, Badih},
title = {{On the Power of Learning from k-Wise Queries}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {41:1--41:32},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.41},
URN = {urn:nbn:de:0030-drops-81801},
doi = {10.4230/LIPIcs.ITCS.2017.41},
annote = {Keywords: Statistical Queries, PAC Learning, Differential Privacy, Lower bounds, Communication Complexity}
}
Document
Detecting communities is Hard (And Counting Them is Even Harder)
Abstract
We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph G, a subset
S of vertices is an (a,b)-community if: * Every member of the community is friends with an (a)-fraction of the community; and
* every non-member is friends with at most a (b)-fraction of the
community.
[Arora, Ge, Sachdeva, Schoenebeck 2012] gave a quasi-polynomial
time algorithm for enumerating all the (a,b)-communities
for any constants a>b.
Here, we prove that, assuming the Exponential Time Hypothesis (ETH),
quasi-polynomial time is in fact necessary - and even for a much weaker
approximation desideratum. Namely, distinguishing between:
* G contains an (1,o(1))-community; and
* G does not contain a (b,b+o(1))-community
for any b.
We also prove that counting the number of (1,o(1))-communities
requires quasi-polynomial time assuming the weaker #ETH.
Cite as
Aviad Rubinstein. Detecting communities is Hard (And Counting Them is Even Harder). In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{rubinstein:LIPIcs.ITCS.2017.42,
author = {Rubinstein, Aviad},
title = {{Detecting communities is Hard (And Counting Them is Even Harder)}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {42:1--42:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.42},
URN = {urn:nbn:de:0030-drops-81496},
doi = {10.4230/LIPIcs.ITCS.2017.42},
annote = {Keywords: Community detection, stable communities, quasipolynomial time}
}
Document
Inherent Trade-Offs in the Fair Determination of Risk Scores
Abstract
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups. We formalize three fairness conditions that lie at the heart of these debates, and we prove that except in highly constrained special cases, there is no method that can satisfy these three conditions simultaneously. Moreover, even satisfying all three conditions approximately requires that the data lie in an approximate version of one of the constrained special cases identified by our theorem. These results suggest some of the ways in which key notions of fairness are incompatible with each other, and hence provide a framework for thinking about the trade-offs between them.
Cite as
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent Trade-Offs in the Fair Determination of Risk Scores. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 43:1-43:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kleinberg_et_al:LIPIcs.ITCS.2017.43,
author = {Kleinberg, Jon and Mullainathan, Sendhil and Raghavan, Manish},
title = {{Inherent Trade-Offs in the Fair Determination of Risk Scores}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {43:1--43:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.43},
URN = {urn:nbn:de:0030-drops-81560},
doi = {10.4230/LIPIcs.ITCS.2017.43},
annote = {Keywords: algorithmic fairness, risk tools, calibration}
}
Document
Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Abstract
Motivated by community detection, we characterise the spectrum of the non-backtracking matrix B in the Degree-Corrected Stochastic Block Model.
Specifically, we consider a random graph on n vertices partitioned into two asymptotically equal-sized clusters. The vertices have i.i.d. weights {\phi_u}_{u=1}^n with second moment \PHItwo. The intra-cluster connection probability for vertices u and v is \frac{\phi_u \phi_v}{n}a and the inter-cluster connection probability is \frac{\phi_u \phi_v}{n}b.
We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix B is asymptotic to \rho = \frac{a+b}{2} \PHItwo. The second eigenvalue is asymptotic to \mu_2 = \frac{a-b}{2} \PHItwo when \mu_2^2 > \rho, but asymptotically bounded by \sqrt{\rho} when \mu_2^2 \leq \rho. All the remaining eigenvalues are asymptotically bounded by \sqrt{\rho}. As a result, a clustering positively-correlated with the true communities can be obtained based on the second eigenvector of B in the regime where \mu_2^2 > \rho.
In a previous work we obtained that detection is impossible when $\mu_2^2 \leq \rho,$ meaning that there occurs a phase-transition in the sparse regime of the Degree-Corrected Stochastic Block Model.
As a corollary, we obtain that Degree-Corrected Erdös-Rényi graphs asymptotically satisfy the graph Riemann hypothesis, a quasi-Ramanujan property.
A by-product of our proof is a weak law of large numbers for local-functionals on Degree-Corrected Stochastic Block Models, which could be of independent interest.
Cite as
Lennart Gulikers, Marc Lelarge, and Laurent Massoulié. Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 44:1-44:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{gulikers_et_al:LIPIcs.ITCS.2017.44,
author = {Gulikers, Lennart and Lelarge, Marc and Massouli\'{e}, Laurent},
title = {{Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {44:1--44:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.44},
URN = {urn:nbn:de:0030-drops-81795},
doi = {10.4230/LIPIcs.ITCS.2017.44},
annote = {Keywords: Degree-Corrected Stochastic Block Model, Non-backtracking Matrix, Machine Learning, Social Networks}
}
Document
Conditional Sparse Linear Regression
Abstract
Machine learning and statistics typically focus on building models that capture the vast majority of the data, possibly ignoring a small subset of data as "noise" or "outliers." By contrast, here we consider the problem of jointly identifying a significant (but perhaps small) segment of a population in which there is a highly sparse linear regression fit, together with the coefficients for the linear fit. We contend that such tasks are of interest both because the models themselves may be able to achieve better predictions in such special cases, but also because they may aid our understanding of the data. We give algorithms for such problems under the sup norm, when this unknown segment of the population is described by a k-DNF condition and the regression fit is s-sparse for constant k and s. For the variants of this problem when the regression fit is not so sparse or using expected error, we also give a preliminary algorithm and highlight the question as a challenge for future work.
Cite as
Brendan Juba. Conditional Sparse Linear Regression. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{juba:LIPIcs.ITCS.2017.45,
author = {Juba, Brendan},
title = {{Conditional Sparse Linear Regression}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {45:1--45:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.45},
URN = {urn:nbn:de:0030-drops-81518},
doi = {10.4230/LIPIcs.ITCS.2017.45},
annote = {Keywords: linear regression, conditional regression, conditional distribution search}
}
Document
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D
Abstract
One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance by Landau et al. gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unresolved, including whether there exist rigorous efficient algorithms when the ground space is degenerate (and poly(n) dimensional), or for the poly(n) lowest energy states for 1D systems, or even whether such states admit succinct classical descriptions or area laws.
In this paper we give a new algorithm for finding low energy states for 1D systems, based on a rigorously justified renormalization group (RG)-type transformation. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n^{O(\log n)} algorithm for the poly(n) lowest energy states for 1D systems (under a mild density condition). We note that for these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is O(nM(n)), where M(n) is the time required to multiply two n by n matrices.
Cite as
Itai Arad, Zeph Landau, Umesh V. Vazirani, and Thomas Vidick. Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{arad_et_al:LIPIcs.ITCS.2017.46,
author = {Arad, Itai and Landau, Zeph and Vazirani, Umesh V. and Vidick, Thomas},
title = {{Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.46},
URN = {urn:nbn:de:0030-drops-81920},
doi = {10.4230/LIPIcs.ITCS.2017.46},
annote = {Keywords: Hamiltonian complexity, area law, gapped ground states, algorithm}
}
Document
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
Abstract
In two-party interactive quantum communication protocols,
we study a recently defined notion of quantum information cost (QIC), which has most of the important properties of its classical analogue (IC). Notably, its link with amortized quantum communication complexity has been used to prove an (almost) tight lower bound on the bounded round quantum complexity of Disjointness.
However, QIC was defined through a purification of the input state. This is valid for fully quantum inputs and tasks but difficult to interpret even for classical tasks.
Also, its link with other notions of information cost that had appeared in the literature was not clear.
We settle both these issues: for quantum communication with classical inputs, we characterize QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an operational interpretation of this new characterization as the sum of the costs of revealing and of forgetting information about the inputs.
To obtain this result, we prove a general Information Flow Lemma assessing the transfer of information in general interactive quantum processes. Specializing this lemma to interactive quantum protocols accomplishing classical tasks, we are able to demistify the link between QIC and other previous notions of information cost in quantum protocols. Furthermore, we clarify the link between QIC and IC by simulating quantumly classical protocols.
Finally, we apply these concepts to argue that any quantum protocol that does not forget information solves Disjointness on n-bits in Omega(n) communication, completely losing the quadratic quantum speedup. Hence forgetting information is here a necessary feature in order to obtain any significant improvement over classical protocols. We also prove that QIC at 0-error
is exactly n for Inner Product, and n (1 - o(1)) for a random Boolean function on n+n bits.
Cite as
Mathieu Laurière and Dave Touchette. The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, p. 47:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{lauriere_et_al:LIPIcs.ITCS.2017.47,
author = {Lauri\`{e}re, Mathieu and Touchette, Dave},
title = {{The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {47:1--47:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.47},
URN = {urn:nbn:de:0030-drops-81898},
doi = {10.4230/LIPIcs.ITCS.2017.47},
annote = {Keywords: Communication Complexity, Information Complexity, Quantum Computation and Information}
}
Document
Overlapping Qubits
Abstract
An ideal system of n qubits has 2^n dimensions. This exponential grants power, but also hinders characterizing the system's state and dynamics. We study a new problem: the qubits in a physical system might not be independent. They can "overlap," in the sense that an operation on one qubit slightly affects the others.
We show that allowing for slight overlaps, n qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be <= epsilon in n^{O(1/epsilon^2)} dimensions.) Thus, even before considering issues like noise, a real system of n qubits might inherently lack any potential for exponential power.
On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.
Cite as
Rui Chao, Ben W. Reichardt, Chris Sutherland, and Thomas Vidick. Overlapping Qubits. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 48:1-48:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{chao_et_al:LIPIcs.ITCS.2017.48,
author = {Chao, Rui and Reichardt, Ben W. and Sutherland, Chris and Vidick, Thomas},
title = {{Overlapping Qubits}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {48:1--48:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.48},
URN = {urn:nbn:de:0030-drops-81826},
doi = {10.4230/LIPIcs.ITCS.2017.48},
annote = {Keywords: Quantum computing, Qubits, Dimension test}
}
Document
Quantum Recommendation Systems
Abstract
A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m \times n preference matrix which is assumed to have a good rank-k approximation, for a small constant k.
In this work, we present a quantum algorithm for recommendation systems that has running time O(\text{poly}(k)\text{polylog}(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.
Cite as
Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kerenidis_et_al:LIPIcs.ITCS.2017.49,
author = {Kerenidis, Iordanis and Prakash, Anupam},
title = {{Quantum Recommendation Systems}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {49:1--49:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.49},
URN = {urn:nbn:de:0030-drops-81541},
doi = {10.4230/LIPIcs.ITCS.2017.49},
annote = {Keywords: Recommendation systems, quantum machine learning, singular value estimation, matrix sampling, quantum algorithms.}
}
Document
Random Walks in Polytopes and Negative Dependence
Abstract
We present a Gaussian random walk in a polytope that starts at a point inside and continues until it gets absorbed at a vertex. Our main result is that the probability distribution induced on the
vertices by this random walk has strong negative dependence properties for matroid polytopes. Such distributions are highly sought after in randomized algorithms as they imply concentration
properties. Our random walk is simple to implement, computationally efficient and can be viewed as an algorithm to round the starting point in an unbiased manner. The proof relies on a simple
inductive argument that synthesizes the combinatorial structure of matroid polytopes with the geometric structure of multivariate Gaussian distributions. Our result not only implies a long
line of past results in a unified and transparent manner, but also implies new results about constructing negatively associated distributions for all matroids.
Cite as
Yuval Peres, Mohit Singh, and Nisheeth K. Vishnoi. Random Walks in Polytopes and Negative Dependence. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{peres_et_al:LIPIcs.ITCS.2017.50,
author = {Peres, Yuval and Singh, Mohit and Vishnoi, Nisheeth K.},
title = {{Random Walks in Polytopes and Negative Dependence}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {50:1--50:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.50},
URN = {urn:nbn:de:0030-drops-81464},
doi = {10.4230/LIPIcs.ITCS.2017.50},
annote = {Keywords: Random walks, Matroid, Polytope, Brownian motion, Negative dependence}
}
Document
Simultaneously Load Balancing for Every p-norm, With Reassignments
Abstract
This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized.
In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms.
For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.
Cite as
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Clifford Stein. Simultaneously Load Balancing for Every p-norm, With Reassignments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bernstein_et_al:LIPIcs.ITCS.2017.51,
author = {Bernstein, Aaron and Kopelowitz, Tsvi and Pettie, Seth and Porat, Ely and Stein, Clifford},
title = {{Simultaneously Load Balancing for Every p-norm, With Reassignments}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.51},
URN = {urn:nbn:de:0030-drops-82009},
doi = {10.4230/LIPIcs.ITCS.2017.51},
annote = {Keywords: Online Matching, Graph Orientation, Minmizing the p-norm}
}
Document
Approximating Approximate Distance Oracles
Abstract
Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v \in V, returns an approximation to the the actual distance between u and v which is within some bounded stretch factor of the true distance. There has been significant work on the tradeoff between the important parameters of approximate distance oracles (and in particular between the size, stretch, and query time), but in this paper we take a different point of view, that of per-instance optimization. If we are given an particular input metric space and stretch bound, can we find the smallest possible approximate distance oracle for that particular input? Since this question is not even well-defined, we restrict our attention to well-known classes of approximate distance oracles, and study whether we can optimize over those classes.
In particular, we give an O(\log n)-approximation to the problem of finding the smallest stretch 3 Thorup-Zwick distance oracle, as well as the problem of finding the smallest P\v{a}tra\c{s}cu-Roditty distance oracle. We also prove a matching \Omega(\log n) lower bound for both problems, and an \Omega(n^{\frac{1}{k}-\frac{1}{2^{k-1}}}) integrality gap for the more general stretch (2k-1) Thorup-Zwick distance oracle. We also consider the problem of approximating the best TZ or PR approximate distance oracle with outliers, and show that more advanced techniques (SDP relaxations in particular) allow us to optimize even in the presence of outliers.
Cite as
Michael Dinitz and Zeyu Zhang. Approximating Approximate Distance Oracles. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dinitz_et_al:LIPIcs.ITCS.2017.52,
author = {Dinitz, Michael and Zhang, Zeyu},
title = {{Approximating Approximate Distance Oracles}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {52:1--52:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.52},
URN = {urn:nbn:de:0030-drops-81692},
doi = {10.4230/LIPIcs.ITCS.2017.52},
annote = {Keywords: distance oracles, approximation algorithms}
}
Document
Fast Cross-Polytope Locality-Sensitive Hashing
Abstract
We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is provably optimal in asymptotic sensitivity and enjoys \mathcal{O}(d \ln d ) hash computation time. Building on a recent result in (Andoni, Indyk, Laarhoven, Razenshteyn '15), we show that optimal asymptotic sensitivity for cross-polytope LSH is retained even when the dense Gaussian matrix is replaced by a fast Johnson-Lindenstrauss transform followed by discrete pseudo-rotation, reducing the hash computation time from \mathcal{O}(d^2) to \mathcal{O}(d \ln d ). Moreover, our scheme achieves the optimal rate of convergence for sensitivity. By incorporating a low-randomness Johnson-Lindenstrauss transform, our scheme can be modified to require only \mathcal{O}(\ln^9(d)) random bits.
Cite as
Christopher Kennedy and Rachel Ward. Fast Cross-Polytope Locality-Sensitive Hashing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kennedy_et_al:LIPIcs.ITCS.2017.53,
author = {Kennedy, Christopher and Ward, Rachel},
title = {{Fast Cross-Polytope Locality-Sensitive Hashing}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.53},
URN = {urn:nbn:de:0030-drops-81936},
doi = {10.4230/LIPIcs.ITCS.2017.53},
annote = {Keywords: Locality-sensitive hashing, Dimension reduction, Johnson-Lindenstrauss lemma}
}
Document
The Distortion of Locality Sensitive Hashing
Abstract
Given a pairwise similarity notion between objects, locality sensitive hashing (LSH) aims to construct a hash function family over the universe of objects such that the probability two objects hash to the same value is their similarity. LSH is a powerful algorithmic tool for large-scale applications and much work has been done to understand LSHable similarities, i.e., similarities that admit an LSH.
In this paper we focus on similarities that are provably non-LSHable and propose a notion of distortion to capture the approximation of such a similarity by a similarity that is LSHable. We consider several well-known non-LSHable similarities and show tight upper and lower bounds on their distortion. We also experimentally show that our upper bounds translate to e
Cite as
Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. The Distortion of Locality Sensitive Hashing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{chierichetti_et_al:LIPIcs.ITCS.2017.54,
author = {Chierichetti, Flavio and Kumar, Ravi and Panconesi, Alessandro and Terolli, Erisa},
title = {{The Distortion of Locality Sensitive Hashing}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {54:1--54:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.54},
URN = {urn:nbn:de:0030-drops-81688},
doi = {10.4230/LIPIcs.ITCS.2017.54},
annote = {Keywords: locality sensitive hashing, distortion, similarity}
}
Document
Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time
Abstract
Let {\mathcal B} be a linear space of matrices over a field {\mathbb spanned by n\times n
matrices B_1, \dots, B_m. The non-commutative rank of {\mathcal B}$ is the minimum r\in {\mathbb N} such that there exists U\leq {\mathbb F}^n satisfying \dim(U)-\dim( {\mathcal B} (U))\geq
n-r, where {\mathcal B}(U):={\mathrm span}(\cup_{i\in[m]} B_i(U)).
Computing the non-commutative rank generalizes some well-known problems including the bipartite graph maximum
matching problem and the linear matroid intersection problem.
In this paper we give a deterministic polynomial-time algorithm to compute the
non-commutative rank over
any field {\mathbb F}. Prior to our work, such
an
algorithm was only known over the rational number field {\mathbb Q}, a result due to Garg et al, [GGOW]. Our algorithm is constructive and produces a witness
certifying the non-commutative rank, a feature that is missing in the algorithm from [GGOW].
Our result is built on techniques which we developed in a previous paper [IQS1], with a new reduction procedure that
helps to keep the blow-up parameter small. There are two ways to realize this
reduction. The first involves constructivizing a key result
of Derksen and Makam [DM2] which they developed in order to prove that the null cone
of matrix semi-invariants is cut out by generators whose degree is polynomial in the size of the matrices involved. We also give a second, simpler method to achieve this. This
gives another proof of the polynomial upper bound on the degree of the generators cutting out the null cone of matrix
semi-invariants.
Both the invariant-theoretic result and the algorithmic result rely crucially
on the regularity lemma proved in [IQS1]. In
this paper we improve on the constructive version of the regularity lemma from [IQS1] by removing a technical coprime
condition that was assumed there.
Cite as
Gábor Ivanyos, Youming Qiao, and K Venkata Subrahmanyam. Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{ivanyos_et_al:LIPIcs.ITCS.2017.55,
author = {Ivanyos, G\'{a}bor and Qiao, Youming and Subrahmanyam, K Venkata},
title = {{Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {55:1--55:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.55},
URN = {urn:nbn:de:0030-drops-81667},
doi = {10.4230/LIPIcs.ITCS.2017.55},
annote = {Keywords: invariant theory, non-commutative rank, null cone, symbolic determinant identity testing, semi-invariants of quivers}
}
Document
The Duality Gap for Two-Team Zero-Sum Games
Abstract
We consider multiplayer games in which the players fall in two teams of size k, with payoffs equal within, and of opposite sign across, the two teams. In the classical case of k=1, such zero-sum games possess a unique value, independent of order of play, due to the von Neumann minimax theorem. However, this fails for all k>1; we can measure this failure by a duality gap, which quantifies the benefit of being the team to commit last to its strategy. In our main result we show that the gap equals 2(1-2^{1-k}) for m=2 and 2(1-\m^{-(1-o(1))k}) for m>2, with m being the size of the action space of each player.
At a finer level, the cost to a team of individual players acting independently while the opposition employs joint randomness is 1-2^{1-k} for k=2, and 1-\m^{-(1-o(1))k} for m>2.
This class of multiplayer games, apart from being a natural bridge between two-player zero-sum games and general multiplayer games, is motivated from Biology (the weak selection model of evolution) and Economics (players with shared utility but poor coordination).
Cite as
Leonard Schulman and Umesh V. Vazirani. The Duality Gap for Two-Team Zero-Sum Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 56:1-56:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{schulman_et_al:LIPIcs.ITCS.2017.56,
author = {Schulman, Leonard and Vazirani, Umesh V.},
title = {{The Duality Gap for Two-Team Zero-Sum Games}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {56:1--56:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.56},
URN = {urn:nbn:de:0030-drops-81429},
doi = {10.4230/LIPIcs.ITCS.2017.56},
annote = {Keywords: multi-player games, duality gap, zero-sum games, evolution}
}
Document
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games
Abstract
In this paper we present a generic reduction from the problem of finding an \epsilon-well-supported Nash equilibrium (WSNE) to that of finding an \Theta(\epsilon)-approximate Nash equilibrium (ANE), in large games with n players and a bounded number of strategies for each player.
Our reduction complements the existing literature on relations between WSNE and ANE, and can be applied to extend hardness results on WSNE to similar results on ANE.
This allows one to focus on WSNE first, which is in general easier to analyze and control in hardness constructions.
As an application we prove a 2^{\Omega(n/\log n)} lower bound on the randomized query complexity of finding an \epsilon-ANE in binary-action n-player games, for some constant \epsilon>0.
This answers an open problem posed by Hart and Nisan and Babichenko, and is very close to the trivial upper bound of 2^n.
Previously for WSNE, Babichenko showed a 2^{\Omega(n)} lower bound on the randomized query complexity of finding an \epsilon-WSNE for some constant epsilon>0.
Our result follows directly from combining Babichenko's result and our new reduction from WSNE to ANE.
Cite as
Xi Chen, Yu Cheng, and Bo Tang. Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 57:1-57:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.ITCS.2017.57,
author = {Chen, Xi and Cheng, Yu and Tang, Bo},
title = {{Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {57:1--57:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.57},
URN = {urn:nbn:de:0030-drops-81636},
doi = {10.4230/LIPIcs.ITCS.2017.57},
annote = {Keywords: Equilibrium Computation, Query Complexity, Large Games}
}
Document
Metatheorems for Dynamic Weighted Matching
Abstract
We consider the maximum weight matching (MWM) problem in dynamic graphs. We provide two reductions. The first reduces the dynamic MWM problem on m-edge, n-node graphs with weights bounded by N to the problem with weights bounded by (n/eps)^2, so that if the MWM problem can be alpha-approximated with update time t(m,n,N), then it can also be (1+eps)alpha-approximated with update time O(t(m,n,(n/eps)^2)log^2 n+log n loglog N)). The second reduction reduces the dynamic MWM problem to the dynamic maximum cardinality matching (MCM) problem in which the graph is unweighted. This reduction shows that if there is an \alpha-approximation algorithm for MCM with update time t(m,n) in m-edge n-node graphs, then there is also a (2+eps)alpha-approximation algorithm for MWM with update time O(t(m,n)eps^{-2}log^2 N). We also obtain better bounds in our reductions if the ratio between the largest and the smallest edge weight is small. Combined with recent work on MCM, these two reductions substantially improve upon the state-of-the-art of dynamic MWM algorithms.
Cite as
Daniel Stubbs and Virginia Vassilevska Williams. Metatheorems for Dynamic Weighted Matching. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{stubbs_et_al:LIPIcs.ITCS.2017.58,
author = {Stubbs, Daniel and Vassilevska Williams, Virginia},
title = {{Metatheorems for Dynamic Weighted Matching}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {58:1--58:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.58},
URN = {urn:nbn:de:0030-drops-81944},
doi = {10.4230/LIPIcs.ITCS.2017.58},
annote = {Keywords: dynamic algorithms, maximum matching, maximum weight matching}
}
Document
SOS Is Not Obviously Automatizable, Even Approximately
Abstract
Suppose we want to minimize a polynomial p(x) = p(x_1,...,x_n), subject to some polynomial constraints q_1(x),...,q_m(x) >_ 0, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include x_i^2 <_ 1 for all 1 <_ i <_ n. It is often stated that the degree-d version of the SOS hierarchy can be solved, to
high accuracy, in time n^O(d). Indeed, I myself have stated this in several previous works.
The point of this note is to state (or remind the reader) that this is not obviously true. The difficulty comes not from the "r" in the Ellipsoid Algorithm, but from the "R"; a priori, we only know an exponential upper bound on the number of bits needed to write down the SOS solution. An explicit example is given of a degree-2 SOS program illustrating the difficulty.
Cite as
Ryan O'Donnell. SOS Is Not Obviously Automatizable, Even Approximately. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 59:1-59:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{odonnell:LIPIcs.ITCS.2017.59,
author = {O'Donnell, Ryan},
title = {{SOS Is Not Obviously Automatizable, Even Approximately}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {59:1--59:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.59},
URN = {urn:nbn:de:0030-drops-81980},
doi = {10.4230/LIPIcs.ITCS.2017.59},
annote = {Keywords: Sum-of-Squares, semidefinite programming}
}
Document
The Journey from NP to TFNP Hardness
Abstract
The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist.
Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of one-way functions, or even public-key cryptography. The only known hardness results are based on less general assumptions such as the existence of collision-resistant hash functions, one-way permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption).
Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP?
In this work, we answer this question and show that hard-on-average TFNP problems can be based on the weak assumption that there exists a hard-on-average language in NP. In particular, this includes the assumption of the existence of one-way functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs.
Cite as
Pavel Hubácek, Moni Naor, and Eylon Yogev. The Journey from NP to TFNP Hardness. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{hubacek_et_al:LIPIcs.ITCS.2017.60,
author = {Hub\'{a}cek, Pavel and Naor, Moni and Yogev, Eylon},
title = {{The Journey from NP to TFNP Hardness}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {60:1--60:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Papadimitriou, Christos H.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.60},
URN = {urn:nbn:de:0030-drops-81627},
doi = {10.4230/LIPIcs.ITCS.2017.60},
annote = {Keywords: TFNP, derandomization, one-way functions, average-case hardness}
}