Volume
LIPIcs, Volume 94
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS)
Event
ITCS 2018, January 11, 2018, Cambridge, MA, USAEditor
Publication Details
- published at: 2018-01-12
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-060-6
- DBLP: db/conf/innovations/innovations2018
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 94, ITCS'18, Complete Volume
Abstract
LIPIcs, Volume 94, ITCS'18, Complete Volume
Cite as
9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@Proceedings{karlin:LIPIcs.ITCS.2018,
title = {{LIPIcs, Volume 94, ITCS'18, Complete Volume}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018},
URN = {urn:nbn:de:0030-drops-84419},
doi = {10.4230/LIPIcs.ITCS.2018},
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
9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{karlin:LIPIcs.ITCS.2018.0,
author = {Karlin, Anna R.},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {0:i--0:xii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.0},
URN = {urn:nbn:de:0030-drops-83104},
doi = {10.4230/LIPIcs.ITCS.2018.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Barriers for Rank Methods in Arithmetic Complexity
Abstract
Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.
At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study.
In this paper we address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (under the name of flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular,
1. Rank methods cannot prove better than (2^d)*n^(d/2) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.)
2. Rank methods cannot prove (d+1)n^(d/2) on the Waring rank of any n-variate polynomial of degree d. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.)
The proofs of these bounds use simple linear-algebraic arguments, leveraging connections between the symbolic rank of matrix polynomials and the usual rank of their evaluations. These techniques can perhaps be extended to barriers for other arithmetic models on which progress has halted.
To see how these barrier results directly inform the state-of-art in arithmetic complexity we note the following.
First, the bounds above nearly match the best explicit bounds we know for these models, hence offer an explanations why the rank methods got stuck there. Second, the bounds above are a far cry (quadratically away) from the true complexity (e.g. of random polynomials) in these models, which if achieved (by any methods), are known to imply super-polynomial formula lower bounds.
We also explain the relation of our barrier results to other attempts, and in particular how they significantly differ from the recent attempts to find analogues of "natural proofs" for arithmetic complexity. Finally, we discuss the few arithmetic lower bound approaches which fall outside rank methods, and some natural directions our barriers suggest.
Cite as
Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2018.1,
author = {Efremenko, Klim and Garg, Ankit and Oliveira, Rafael and Wigderson, Avi},
title = {{Barriers for Rank Methods in Arithmetic Complexity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {1:1--1:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.1},
URN = {urn:nbn:de:0030-drops-83506},
doi = {10.4230/LIPIcs.ITCS.2018.1},
annote = {Keywords: Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity}
}
Document
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Abstract
Suppose \varphi and \psi are two angles satisfying \tan(\varphi) = 2 \tan(\psi) > 0. We prove that under this condition \varphi and \psi cannot be both rational multiples of \pi. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time
computable, (2) \#P-hard in general but polynomial time computable
on planar graphs, and (3) \#P-hard on planar graphs. In particular problems in (2) are precisely those that can be transformed to a form solvable by the Fisher-Kasteleyn-Temperley algorithm by a holographic reduction.
Cite as
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk. A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cai_et_al:LIPIcs.ITCS.2018.2,
author = {Cai, Jin-Yi and Fu, Zhiguo and Girstmair, Kurt and Kowalczyk, Michael},
title = {{A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {2:1--2:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.2},
URN = {urn:nbn:de:0030-drops-83251},
doi = {10.4230/LIPIcs.ITCS.2018.2},
annote = {Keywords: Spin Systems, Holant Problems, Number Theory, Characters, Cyclotomic Fields}
}
Document
Quantum Query Algorithms are Completely Bounded Forms
Abstract
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms.
Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms.
We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
Cite as
Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2018.3,
author = {Arunachalam, Srinivasan and Bri\"{e}t, Jop and Palazuelos, Carlos},
title = {{Quantum Query Algorithms are Completely Bounded Forms}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {3:1--3:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.3},
URN = {urn:nbn:de:0030-drops-83383},
doi = {10.4230/LIPIcs.ITCS.2018.3},
annote = {Keywords: Quantum query algorithms, operator space theory, polynomial method, approximate degree.}
}
Document
A Complete Characterization of Unitary Quantum Space
Abstract
Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded 2^k(n) x 2^k(n) matrix is complete for the class of problems solvable by quantum circuits acting on O(k(n)) qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian 2^k(n) x 2^k(n) matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results.
Additionally, as a consequence we show that preciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states.
Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.
Cite as
Bill Fefferman and Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quantum Space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fefferman_et_al:LIPIcs.ITCS.2018.4,
author = {Fefferman, Bill and Lin, Cedric Yen-Yu},
title = {{A Complete Characterization of Unitary Quantum Space}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {4:1--4:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.4},
URN = {urn:nbn:de:0030-drops-83242},
doi = {10.4230/LIPIcs.ITCS.2018.4},
annote = {Keywords: Quantum complexity, space complexity, complete problems, QMA}
}
Document
Matrix Completion and Related Problems via Strong Duality
Abstract
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and show that under certain dual conditions, the optimal solution of the matrix factorization program is the same as its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization problems are hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly.
We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis (PCA). These are examples of efficiently recovering a hidden matrix given limited reliable observations of it. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity guarantees for matrix completion and robust PCA.
Cite as
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, and Hongyang Zhang. Matrix Completion and Related Problems via Strong Duality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{balcan_et_al:LIPIcs.ITCS.2018.5,
author = {Balcan, Maria-Florina and Liang, Yingyu and Woodruff, David P. and Zhang, Hongyang},
title = {{Matrix Completion and Related Problems via Strong Duality}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {5:1--5:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.5},
URN = {urn:nbn:de:0030-drops-83583},
doi = {10.4230/LIPIcs.ITCS.2018.5},
annote = {Keywords: Non-Convex Optimization, Strong Duality, Matrix Completion, Robust PCA, Sample Complexity}
}
Document
A Quasi-Random Approach to Matrix Spectral Analysis
Abstract
Inspired by quantum computing algorithms for Linear Algebra problems [Harrow et al., Phys. Rev. Lett. 2009, Ta-Shma, STOC 2013] we study how simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log^2(n)) parallel time with a total cost of O(n^(\omega+1)) Boolean operations. This Boolean complexity matches the best known O(log^2(n)) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so it may lead to actual implementations, allowing fast parallel computation of eigenvectors and eigenvalues in practice.
Previous approaches to solve the Eigen-Problem generally use randomization to avoid bad conditions - as we do. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod 2pi) is the main technical contribution of this work. It relies on the theory of low-discrepancy or quasi-random sequences - a theory, which to the best of our knowledge, has not been connected thus far to linear algebra problems. Hence, we believe that further study of this new connection will lead to additional improvements.
Cite as
Michael Ben-Or and Lior Eldar. A Quasi-Random Approach to Matrix Spectral Analysis. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{benor_et_al:LIPIcs.ITCS.2018.6,
author = {Ben-Or, Michael and Eldar, Lior},
title = {{A Quasi-Random Approach to Matrix Spectral Analysis}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {6:1--6:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.6},
URN = {urn:nbn:de:0030-drops-83288},
doi = {10.4230/LIPIcs.ITCS.2018.6},
annote = {Keywords: linear algebra, eigenvalues, eigenvectors, low-discrepancy sequence}
}
Document
Non-Negative Sparse Regression and Column Subset Selection with L1 Error
Abstract
We consider the problems of sparse regression and column subset selection under L1 error. For both problems, we show that in the non-negative setting it is possible to obtain tight and efficient approximations, without any additional structural assumptions (such as restricted isometry, incoherence, expansion, etc.). For sparse regression, given a matrix A and a vector b with non-negative entries, we give an efficient algorithm to output a vector x of sparsity O(k), for which |Ax - b|_1 is comparable to the smallest error possible using non-negative k-sparse x. We then use this technique to obtain our main result: an efficient algorithm for column subset selection under L1 error for non-negative matrices.
Cite as
Aditya Bhaskara and Silvio Lattanzi. Non-Negative Sparse Regression and Column Subset Selection with L1 Error. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bhaskara_et_al:LIPIcs.ITCS.2018.7,
author = {Bhaskara, Aditya and Lattanzi, Silvio},
title = {{Non-Negative Sparse Regression and Column Subset Selection with L1 Error}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.7},
URN = {urn:nbn:de:0030-drops-83548},
doi = {10.4230/LIPIcs.ITCS.2018.7},
annote = {Keywords: Sparse regression, L1 error optimization, Column subset selection}
}
Document
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Abstract
Understanding the singular value spectrum of an n x n matrix A is a fundamental task in countless numerical computation and data analysis applications. In matrix multiplication time, it is possible to perform a full SVD of A and directly compute the singular values \sigma_1,...,\sigma_n. However, little is known about algorithms that break this runtime barrier.
Using tools from stochastic trace estimation, polynomial approximation, and fast linear system solvers, we show how to efficiently isolate different ranges of A's spectrum and approximate the number of singular values in these ranges. We thus effectively compute an approximate histogram of the spectrum, which can stand in for the true singular values in many applications.
We use our histogram primitive to give the first algorithms for approximating a wide class of symmetric matrix norms and spectral sums faster than the best known runtime for matrix multiplication. For example, we show how to obtain a (1 + \epsilon) approximation to the Schatten 1-norm (i.e. the nuclear or trace norm) in just ~ O((nnz(A)n^{1/3} + n^2)\epsilon^{-3}) time for A with uniform row sparsity or \tilde O(n^{2.18} \epsilon^{-3}) time for dense matrices. The runtime scales smoothly for general Schatten-p norms, notably becoming \tilde O (p nnz(A) \epsilon^{-3}) for any real p >= 2.
At the same time, we show that the complexity of spectrum approximation is inherently tied to fast matrix multiplication in the small \epsilon regime. We use fine-grained complexity to give conditional lower bounds for spectrum approximation, showing that achieving milder \epsilon dependencies in our algorithms would imply triangle detection algorithms for general graphs running in faster than state of the art matrix multiplication time. This further implies, through a reduction of (Williams & William, 2010), that highly accurate spectrum approximation algorithms running in subcubic time can be used to give subcubic time matrix multiplication. As an application of our bounds, we show that precisely computing all effective resistances in a graph in less than matrix multiplication time is likely difficult, barring a major algorithmic breakthrough.
Cite as
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{musco_et_al:LIPIcs.ITCS.2018.8,
author = {Musco, Cameron and Netrapalli, Praneeth and Sidford, Aaron and Ubaru, Shashanka and Woodruff, David P.},
title = {{Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {8:1--8:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.8},
URN = {urn:nbn:de:0030-drops-83397},
doi = {10.4230/LIPIcs.ITCS.2018.8},
annote = {Keywords: spectrum approximation, matrix norm computation, fine-grained complexity, linear algebra}
}
Document
Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs
Abstract
As a natural extension of the SAT problem, an array of proof systems for quantified Boolean formulas (QBF) have been proposed, many of which extend a propositional proof system to handle universal quantification. By formalising the construction of the QBF proof system obtained from a propositional proof system by adding universal reduction (Beyersdorff, Bonacina & Chew, ITCS'16), we present a new technique for proving proof-size lower bounds in these systems. The technique relies only on two semantic measures: the cost of a QBF, and the capacity of a proof. By examining the capacity of proofs in several QBF systems, we are able to use the technique to obtain lower bounds based on cost alone. As applications of the technique, we first prove exponential lower bounds for a new family of simple QBFs representing equality. The main application is in proving exponential lower bounds with high probability for a class of randomly generated QBFs, the first 'genuine' lower bounds of this kind, which apply to the QBF analogues of resolution, Cutting Planes, and Polynomial Calculus. Finally, we employ the technique to give a simple proof of hardness for a prominent family of QBFs.
Cite as
Olaf Beyersdorff, Joshua Blinkhorn, and Luke Hinde. Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{beyersdorff_et_al:LIPIcs.ITCS.2018.9,
author = {Beyersdorff, Olaf and Blinkhorn, Joshua and Hinde, Luke},
title = {{Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {9:1--9:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.9},
URN = {urn:nbn:de:0030-drops-83228},
doi = {10.4230/LIPIcs.ITCS.2018.9},
annote = {Keywords: quantified Boolean formulas, proof complexity, lower bounds}
}
Document
Stabbing Planes
Abstract
We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by branching on an inequality and its "integer negation." That is, we can (nondeterministically choose) a hyperplane a x >= b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying a x >= b, the points satisfying a x <= b-1, and the middle slab b-1 < a x < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show somewhat surprisingly that Stabbing Planes can efficiently simulate Cutting Planes, and moreover, is strictly stronger than Cutting Planes under a reasonable conjecture. We prove linear lower bounds on the rank of Stabbing Planes refutations, by adapting
a lifting argument in communication complexity.
Cite as
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, and Robert Robere. Stabbing Planes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{beame_et_al:LIPIcs.ITCS.2018.10,
author = {Beame, Paul and Fleming, Noah and Impagliazzo, Russell and Kolokolova, Antonina and Pankratov, Denis and Pitassi, Toniann and Robere, Robert},
title = {{Stabbing Planes}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {10:1--10:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.10},
URN = {urn:nbn:de:0030-drops-83418},
doi = {10.4230/LIPIcs.ITCS.2018.10},
annote = {Keywords: Complexity Theory, Proof Complexity, Communication Complexity, Cutting Planes, Semi-Algebraic Proof Systems, Pseudo Boolean Solvers, SAT solvers, Inte}
}
Document
A Candidate for a Strong Separation of Information and Communication
Abstract
The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C).
We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I=polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C)=polylog(C).
Cite as
Mark Braverman, Anat Ganor, Gillat Kol, and Ran Raz. A Candidate for a Strong Separation of Information and Communication. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.ITCS.2018.11,
author = {Braverman, Mark and Ganor, Anat and Kol, Gillat and Raz, Ran},
title = {{A Candidate for a Strong Separation of Information and Communication}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {11:1--11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.11},
URN = {urn:nbn:de:0030-drops-83322},
doi = {10.4230/LIPIcs.ITCS.2018.11},
annote = {Keywords: communication complexity, amortized communication complexity, communication compression, direct sum, information complexity}
}
Document
Information Value of Two-Prover Games
Abstract
We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) - in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective input. We study the trade-off between the information cost of the protocol and the achieved value of the game after the protocol.
In particular, we show the connection of this trade-off and the amortized behavior of the game (i.e. repeated value of the game).
We show that if one can win the game with at least (1 - \epsilon)-probability by communicating at most \epsilon bits of information,
then one can win n copies with probability at least 2^{-O(\epsilon n)}. This gives an intuitive explanation why Raz's counter-example to strong parallel repetition [Raz2008] (the odd cycle game) is a counter-example to strong parallel repetition - one can win the odd-cycle game on a cycle of length $m$ by communicating O(m^{-2})-bits where m is the number of vertices.
Conversely, for projection games, we show that if one can win n copies with probability larger than (1-\epsilon)^n,
then one can win one copy with at least (1 - O(\epsilon))-probability by communicating O(\epsilon) bits of information.
By showing the equivalence between information value and amortized value, we give an alternative direction for further works in studying amortized behavior of the two-prover games.
The main technical tool is the "Chi-Squared Lemma" which bounds the information cost of the protocol in terms of Chi-Squared distance,
instead of usual divergence. This avoids the square loss from using Pinsker's Inequality.
Cite as
Mark Braverman and Young Kun Ko. Information Value of Two-Prover Games. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.ITCS.2018.12,
author = {Braverman, Mark and Ko, Young Kun},
title = {{Information Value of Two-Prover Games}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.12},
URN = {urn:nbn:de:0030-drops-83466},
doi = {10.4230/LIPIcs.ITCS.2018.12},
annote = {Keywords: Two Prover Game, Parallel Repetition, Odd-Cycle Game, Amortized Value of the Game}
}
Document
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Abstract
In this paper, we propose a new mechanism - the Disagreement Mechanism - which elicits privately-held, non-variable information from self-interested agents in the single question (peer-prediction) setting.
To the best of our knowledge, our Disagreement Mechanism is the first strictly truthful mechanism in the single-question setting that is simultaneously:
- Detail-Free: does not need to know the common prior;
- Focal: truth-telling pays strictly higher than any other symmetric equilibria excluding some unnatural permutation equilibria;
- Small group: the properties of the mechanism hold even for a small number of agents, even in binary signal setting. Our mechanism only asks each agent her signal as well as a forecast of the other agents' signals.
Additionally, we show that the focal result is both tight and robust, and we extend it to the case of asymmetric equilibria when the number of agents is sufficiently large.
Cite as
Yuqing Kong and Grant Schoenebeck. Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kong_et_al:LIPIcs.ITCS.2018.13,
author = {Kong, Yuqing and Schoenebeck, Grant},
title = {{Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {13:1--13:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.13},
URN = {urn:nbn:de:0030-drops-83174},
doi = {10.4230/LIPIcs.ITCS.2018.13},
annote = {Keywords: peer prediction, equilibrium selection, information theory}
}
Document
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
Abstract
Prediction markets provide a unique and compelling way to sell and aggregate information, yet a good understanding of optimal strategies for agents participating in such markets remains elusive. To model this complex setting, prior work proposes a three stages game called the Alice Bob Alice (A-B-A) game - Alice participates in the market first, then Bob joins, and then Alice has a chance to participate again. While prior work has made progress in classifying the optimal strategy for certain interesting edge cases, it remained an open question to calculate Alice's best strategy in the A-B-A game for a general information structure.
In this paper, we analyze the A-B-A game for a general information structure and (1) show a "revelation-principle" style result: it is enough for Alice to use her private signal space as her announced signal space, that is, Alice cannot gain more by revealing her information more "finely"; (2) provide a FPTAS to compute the optimal information revelation strategy with additive error when Alice's information is a signal from a constant-sized set; (3) show that sometimes it is better for Alice to reveal partial information in the first stage even if Alice's information is a single binary bit.
Cite as
Yuqing Kong and Grant Schoenebeck. Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kong_et_al:LIPIcs.ITCS.2018.14,
author = {Kong, Yuqing and Schoenebeck, Grant},
title = {{Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {14:1--14:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.14},
URN = {urn:nbn:de:0030-drops-83191},
doi = {10.4230/LIPIcs.ITCS.2018.14},
annote = {Keywords: prediction market, information revelation, optimization}
}
Document
An Axiomatic Study of Scoring Rule Markets
Abstract
Prediction markets are well-studied in the case where predictions are probabilities or expectations of future random variables. In 2008, Lambert, et al. proposed a generalization, which we call "scoring rule markets" (SRMs), in which traders predict the value of arbitrary statistics of the random variables, provided these statistics can be elicited by a scoring rule. Surprisingly, despite active recent work on prediction markets, there has not yet been any investigation into more general SRMs. To initiate such a study, we ask the following question: in what sense are SRMs "markets"? We classify SRMs according to several axioms that capture potentially desirable qualities of a market, such as the ability to freely exchange goods (contracts) for money. Not all SRMs satisfy our axioms: once a contract is purchased in any market for prediction the median of some variable, there will not necessarily be any way to sell that contract back, even in a very weak sense. Our main result is a characterization showing that slight generalizations of cost-function-based markets are the only markets to satisfy all of our axioms for finite-outcome random variables. Nonetheless, we find that several SRMs satisfy weaker versions of our axioms, including a novel share-based market mechanism for ratios of expected values.
Cite as
Rafael Frongillo and Bo Waggoner. An Axiomatic Study of Scoring Rule Markets. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{frongillo_et_al:LIPIcs.ITCS.2018.15,
author = {Frongillo, Rafael and Waggoner, Bo},
title = {{An Axiomatic Study of Scoring Rule Markets}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {15:1--15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.15},
URN = {urn:nbn:de:0030-drops-83611},
doi = {10.4230/LIPIcs.ITCS.2018.15},
annote = {Keywords: prediction markets, information elicitation, scoring rules}
}
Document
On Price versus Quality
Abstract
In this work we propose a model where the value of a buyer for some
product (like a slice of pizza) is a combination of their personal
desire for the product (how hungry they are for pizza) and the
quality of the product (how good the pizza is). Sellers in this
setting have a two-dimensional optimization problem of determining
both the quality level at which to make their product (how expensive
ingredients to use) and the price at which to sell it. We analyze
optimal seller strategies as well as analogs of Walrasian equilibria
in this setting. A key question we are interested in is: to what
extent will the price of a good be a reliable indicator of the
good's quality?
One result we show is that indeed in this model, price will be a
surprisingly robust signal for quality under optimal seller
behavior. In particular, while the specific quality and price that
a seller should choose will depend highly on the specific
distribution of buyers, for optimal sellers, price and quality will
be linearly related, independent of that distribution. We also show
that for the case of multiple buyers and sellers, an analog of
Walrasian equilibrium exists in this setting, and can be found via a
natural tatonnement process. Finally, we analyze markets with a combination of "locals" (who know the quality of each good) and "tourists" (who do not) and analyze under what conditions the market will become a tourist trap, setting quality to zero while keeping prices high.
Cite as
Avrim Blum and Yishay Mansour. On Price versus Quality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{blum_et_al:LIPIcs.ITCS.2018.16,
author = {Blum, Avrim and Mansour, Yishay},
title = {{On Price versus Quality}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {16:1--16:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.16},
URN = {urn:nbn:de:0030-drops-83264},
doi = {10.4230/LIPIcs.ITCS.2018.16},
annote = {Keywords: Algorithmic game theory, pricing, Cobb-Douglas valuations}
}
Document
Pseudo-Deterministic Proofs
Abstract
We introduce pseudo-deterministic interactive proofs (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.
We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier.
Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one.
The IP=PSPACE characterization implies that psdIP = IP. The challenge is to find constant round pseudo-deterministic interactive proofs for hard search problems. We show a constant round pseudo-deterministic interactive proof for the graph isomorphism problem: on any input pair of isomorphic graphs (G_0,G_1), there exist a unique isomorphism phi from G_0 to G_1 (although many isomorphism many exist) which will be output by the verifier with high probability, regardless of any dishonest prover strategy.
In contrast, we show that it is unlikely that psdIP proofs with constant rounds exist for NP-complete problems by showing that if any NP-complete problem has a constant round psdIP protocol, then the polynomial hierarchy collapses.
Cite as
Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-Deterministic Proofs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2018.17,
author = {Goldwasser, Shafi and Grossman, Ofer and Holden, Dhiraj},
title = {{Pseudo-Deterministic Proofs}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {17:1--17:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.17},
URN = {urn:nbn:de:0030-drops-83669},
doi = {10.4230/LIPIcs.ITCS.2018.17},
annote = {Keywords: Pseudo-Deterministic, Interactive Proofs}
}
Document
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
Abstract
A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.
We present direct constructions of doubly-efficient interactive proof systems for problems in P that are believed to have relatively high complexity. Specifically, such constructions are presented for t-CLIQUE and t-SUM. In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC). The proof systems presented by us are significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016), and can be implemented using a smaller number of rounds.
Cite as
Oded Goldreich and Guy N. Rothblum. Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{goldreich_et_al:LIPIcs.ITCS.2018.18,
author = {Goldreich, Oded and Rothblum, Guy N.},
title = {{Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {18:1--18:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.18},
URN = {urn:nbn:de:0030-drops-83279},
doi = {10.4230/LIPIcs.ITCS.2018.18},
annote = {Keywords: Interactive proofs}
}
Document
Zero-Knowledge Proofs of Proximity
Abstract
Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear in the input length. Since the verifier cannot even read the entire input, following the property testing literature, we only require that the verifier reject inputs that are far from the language (and, as usual, accept inputs that are in the language).
In this work, we initiate the study of zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zero-knowledge property. Specifically, the verifier learns nothing beyond (1) the fact that the input is in the language, and (2) what it could additionally infer by reading a few bits of the input.
Our main focus is the setting of statistical zero-knowledge where we show that the following hold unconditionally (where N denotes the input length):
- Statistical ZKPPs can be sub-exponentially more efficient than property testers (or even non-interactive IPPs): We show a natural property which has a statistical ZKPP with a polylog(N) time verifier, but requires Omega(sqrt(N)) queries (and hence also runtime) for every property tester.
- Statistical ZKPPs can be sub-exponentially less efficient than IPPs: We show a property which has an IPP with a polylog(N) time verifier, but cannot have a statistical ZKPP with even an N^(o(1)) time verifier.
- Statistical ZKPPs for some graph-based properties such as promise versions of expansion and bipartiteness, in the bounded degree graph model, with polylog(N) time verifiers exist.
Lastly, we also consider the computational setting where we show that:
- Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) sqrt(N) time verifier.
- Assuming the existence of collision-resistant hash functions, every language in NP has a statistical zero-knowledge argument of proximity with a polylog(N) time verifier.
Cite as
Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-Knowledge Proofs of Proximity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{berman_et_al:LIPIcs.ITCS.2018.19,
author = {Berman, Itay and Rothblum, Ron D. and Vaikuntanathan, Vinod},
title = {{Zero-Knowledge Proofs of Proximity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {19:1--19:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.19},
URN = {urn:nbn:de:0030-drops-83575},
doi = {10.4230/LIPIcs.ITCS.2018.19},
annote = {Keywords: Property Testing, Interactive Proofs, Zero-Knowledge}
}
Document
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Abstract
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
Cite as
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{allender_et_al:LIPIcs.ITCS.2018.20,
author = {Allender, Eric and Grochow, Joshua A. and van Melkebeek, Dieter and Moore, Cristopher and Morgan, Andrew},
title = {{Minimum Circuit Size, Graph Isomorphism, and Related Problems}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.20},
URN = {urn:nbn:de:0030-drops-83455},
doi = {10.4230/LIPIcs.ITCS.2018.20},
annote = {Keywords: Reductions between NP-intermediate problems, Graph Isomorphism, Minimum Circuit Size Problem, time-bounded Kolmogorov complexity}
}
Document
Foundations of Homomorphic Secret Sharing
Abstract
Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open.
We initiate a systematic study of HSS, making the following contributions.
- A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework.
- Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer.
- Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.
Cite as
Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. Foundations of Homomorphic Secret Sharing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{boyle_et_al:LIPIcs.ITCS.2018.21,
author = {Boyle, Elette and Gilboa, Niv and Ishai, Yuval and Lin, Huijia and Tessaro, Stefano},
title = {{Foundations of Homomorphic Secret Sharing}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {21:1--21:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.21},
URN = {urn:nbn:de:0030-drops-83659},
doi = {10.4230/LIPIcs.ITCS.2018.21},
annote = {Keywords: Cryptography, homomorphic secret sharing, secure computation, communication complexity, worst-case to average case reductions.}
}
Document
Convergence Results for Neural Networks via Electrodynamics
Abstract
We study whether a depth two neural network can learn another
depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient descent converges to the target function is equivalent to the following question in electrodynamics: Given k fixed protons in R^d, and k electrons, each moving due to the attractive force from the protons and repulsive force from the remaining electrons, whether at equilibrium all the electrons will be matched up with the protons, up to a permutation. Under the standard electrical force, this follows from the classic Earnshaw's theorem. In our setting,
the force is determined by the activation function and the
input distribution. Building on this equivalence, we prove the
existence of an activation function such that gradient descent learns at least one of the hidden nodes in the target network.
Iterating, we show that gradient descent can be used to learn the entire network one node at a time.
Cite as
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, and Qiuyi Zhang. Convergence Results for Neural Networks via Electrodynamics. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{panigrahy_et_al:LIPIcs.ITCS.2018.22,
author = {Panigrahy, Rina and Rahimi, Ali and Sachdeva, Sushant and Zhang, Qiuyi},
title = {{Convergence Results for Neural Networks via Electrodynamics}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {22:1--22:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.22},
URN = {urn:nbn:de:0030-drops-83521},
doi = {10.4230/LIPIcs.ITCS.2018.22},
annote = {Keywords: Deep Learning, Learning Theory, Non-convex Optimization}
}
Document
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
Abstract
We provide a novel accelerated first-order method that achieves the asymptotically optimal convergence rate for smooth functions in the first-order oracle model. To this day, Nesterov's Accelerated Gradient Descent (AGD) and variations thereof were the only methods achieving acceleration in this standard blackbox model. In contrast, our algorithm is significantly different from AGD, as it relies on a predictor-corrector approach similar to that used by Mirror-Prox [Nemirovski, 2004] and Extra-Gradient Descent [Korpelevich, 1977] in the solution of convex-concave saddle point problems. For this reason, we dub our algorithm Accelerated Extra-Gradient Descent (AXGD).
Its construction is motivated by the discretization of an accelerated continuous-time dynamics [Krichene et al., 2015] using the classical method of implicit Euler discretization. Our analysis explicitly shows the effects of discretization through a conceptually novel primal-dual viewpoint. Moreover, we show that the method is quite general: it attains optimal convergence rates for other classes of objectives (e.g., those with generalized smoothness properties or that are non-smooth and Lipschitz-continuous) using the appropriate choices of step lengths. Finally, we present experiments showing that our algorithm matches the performance of Nesterov's method, while appearing more robust to noise in some cases.
Cite as
Jelena Diakonikolas and Lorenzo Orecchia. Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{diakonikolas_et_al:LIPIcs.ITCS.2018.23,
author = {Diakonikolas, Jelena and Orecchia, Lorenzo},
title = {{Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {23:1--23:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.23},
URN = {urn:nbn:de:0030-drops-83562},
doi = {10.4230/LIPIcs.ITCS.2018.23},
annote = {Keywords: Acceleration, dynamical systems, discretization, first-order methods}
}
Document
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory
Abstract
Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently.
In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem.
This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling.
Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems.
Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).
Cite as
Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{burgisser_et_al:LIPIcs.ITCS.2018.24,
author = {B\"{u}rgisser, Peter and Garg, Ankit and Oliveira, Rafael and Walter, Michael and Wigderson, Avi},
title = {{Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {24:1--24:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.24},
URN = {urn:nbn:de:0030-drops-83510},
doi = {10.4230/LIPIcs.ITCS.2018.24},
annote = {Keywords: alternating minimization, tensors, scaling, quantum marginal problem, null cone, invariant theory, geometric complexity theory}
}
Document
Further Limitations of the Known Approaches for Matrix Multiplication
Abstract
We consider the techniques behind the current best algorithms for matrix multiplication. Our results are threefold.
(1) We provide a unifying framework, showing that all known matrix multiplication running times since 1986 can be achieved from a single very natural tensor - the structural tensor T_q of addition modulo an integer q.
(2) We show that if one applies a generalization of the known techniques (arbitrary zeroing out of tensor powers to obtain independent matrix products in order to use the asymptotic sum inequality of Schönhage) to an arbitrary monomial degeneration of T_q, then there is an explicit lower bound, depending on q, on the bound on the matrix multiplication exponent omega that one can achieve. We also show upper bounds on the value alpha that one can achieve, where alpha is such that n * n^alpha * n matrix multiplication can be computed in n^{2+o(1)} time.
(3) We show that our lower bound on omega approaches 2 as q goes to infinity. This suggests a promising approach to improving the bound on omega: for variable q, find a monomial degeneration of T_q which, using the known techniques, produces an upper bound on omega as a function of q. Then, take q to infinity. It is not ruled out, and hence possible, that one can obtain omega=2 in this way.
Cite as
Josh Alman and Virginia Vassilevska Williams. Further Limitations of the Known Approaches for Matrix Multiplication. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{alman_et_al:LIPIcs.ITCS.2018.25,
author = {Alman, Josh and Vassilevska Williams, Virginia},
title = {{Further Limitations of the Known Approaches for Matrix Multiplication}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {25:1--25:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.25},
URN = {urn:nbn:de:0030-drops-83609},
doi = {10.4230/LIPIcs.ITCS.2018.25},
annote = {Keywords: matrix multiplication, lower bound, monomial degeneration, structural tensor of addition mod p}
}
Document
Local Decoding and Testing of Polynomials over Grids
Abstract
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that n-variate polynomials of total degree at most d over grids, i.e. sets of the form A_1 \times A_2 \times \cdots \times A_n, form error-correcting codes (of distance at least 2^{-d} provided \min_i\{|A_i|\}\geq 2). In this work we explore their local decodability and local testability. While these aspects have been studied extensively when A_1 = \cdots = A_n = \F_q are the same finite field, the setting when A_i's are not the full field does not seem to have been explored before.
In this work we focus on the case A_i = {0,1} for every i. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable.
Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
Cite as
Srikanth Srinivasan and Madhu Sudan. Local Decoding and Testing of Polynomials over Grids. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{srinivasan_et_al:LIPIcs.ITCS.2018.26,
author = {Srinivasan, Srikanth and Sudan, Madhu},
title = {{Local Decoding and Testing of Polynomials over Grids}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {26:1--26:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.26},
URN = {urn:nbn:de:0030-drops-83294},
doi = {10.4230/LIPIcs.ITCS.2018.26},
annote = {Keywords: Property testing, Coding theory, Low-degree testing, Local decoding, Local testing}
}
Document
Relaxed Locally Correctable Codes
Abstract
Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.
A natural relaxation of LDCs, introduced by Ben-Sasson et al. (SICOMP, 2006), allows the decoder to reject (i.e., refuse to answer) in case it detects that the codeword is corrupt. They call such a decoder a relaxed decoder and construct a constant-query relaxed LDC with almost-linear blocklength, which is sub-exponentially better than what is known for (full-fledged) LDCs in the constant-query regime.
We consider an analogous relaxation for local correction. Thus, a relaxed local corrector reads only few bits from a (possibly) corrupt codeword and either recovers the desired bit of the codeword, or rejects in case it detects a corruption.
We give two constructions of relaxed LCCs in two regimes, where the first optimizes the query complexity and the second optimizes the rate:
1. Constant Query Complexity: A relaxed LCC with polynomial blocklength whose corrector only reads a constant number of bits of the codeword. This is a sub-exponential improvement over the best constant query (full-fledged) LCCs that are known.
2. Constant Rate: A relaxed LCC with constant rate (i.e., linear blocklength) with quasi-polylogarithmic query complexity. This is a nearly sub-exponential improvement over the query complexity of a recent (full-fledged) constant-rate LCC of Kopparty et al. (STOC, 2016).
Cite as
Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed Locally Correctable Codes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gur_et_al:LIPIcs.ITCS.2018.27,
author = {Gur, Tom and Ramnarayan, Govind and Rothblum, Ron D.},
title = {{Relaxed Locally Correctable Codes}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {27:1--27:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.27},
URN = {urn:nbn:de:0030-drops-83154},
doi = {10.4230/LIPIcs.ITCS.2018.27},
annote = {Keywords: Keywords and phrases Coding Theory, Locally Correctable Codes, Probabilistically Checkable Proofs}
}
Document
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Abstract
With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses graph. We prove that any hypothesis class whose hypotheses graph is mixing cannot be learned using less than Omega(log^2 |H|) memory bits unless the learner uses at least a large number |H|^Omega(1) labeled examples. Our work builds on a combinatorial framework that we suggested in a previous work for proving lower bounds on space bounded learning. The strong lower bound is obtained by defining a new notion of pseudorandomness, the entropy sampler. Raz obtained a similar result using different ideas.
Cite as
Dana Moshkovitz and Michal Moshkovitz. Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{moshkovitz_et_al:LIPIcs.ITCS.2018.28,
author = {Moshkovitz, Dana and Moshkovitz, Michal},
title = {{Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {28:1--28:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.28},
URN = {urn:nbn:de:0030-drops-83374},
doi = {10.4230/LIPIcs.ITCS.2018.28},
annote = {Keywords: learning, space bound, mixing, certainty, entropy sampler}
}
Document
Pseudorandom Generators for Low Sensitivity Functions
Abstract
A Boolean function is said to have maximal sensitivity s if s is the largest number of Hamming neighbors of a point which differ from it in function value. We initiate the study of pseudorandom generators fooling low-sensitivity functions as an intermediate step towards settling the sensitivity conjecture. We construct a pseudorandom generator with seed-length 2^{O(s^{1/2})} log(n) that fools Boolean functions on n variables with maximal sensitivity at most s. Prior to our work, the (implicitly) best pseudorandom generators for this class of functions required seed-length 2^{O(s)} log(n).
Cite as
Pooya Hatami and Avishay Tal. Pseudorandom Generators for Low Sensitivity Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hatami_et_al:LIPIcs.ITCS.2018.29,
author = {Hatami, Pooya and Tal, Avishay},
title = {{Pseudorandom Generators for Low Sensitivity Functions}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.29},
URN = {urn:nbn:de:0030-drops-83300},
doi = {10.4230/LIPIcs.ITCS.2018.29},
annote = {Keywords: Pseudorandom Generators, Sensitivity, Sensitivity Conjecture}
}
Document
Scheduling with Explorable Uncertainty
Abstract
We introduce a novel model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit p'_j (which is the time taken to execute the job if it is not tested) to any value between 0 and p'_j. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
Cite as
Christoph Dürr, Thomas Erlebach, Nicole Megow, and Julie Meißner. Scheduling with Explorable Uncertainty. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{durr_et_al:LIPIcs.ITCS.2018.30,
author = {D\"{u}rr, Christoph and Erlebach, Thomas and Megow, Nicole and Mei{\ss}ner, Julie},
title = {{Scheduling with Explorable Uncertainty}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.30},
URN = {urn:nbn:de:0030-drops-83360},
doi = {10.4230/LIPIcs.ITCS.2018.30},
annote = {Keywords: online scheduling, explorable uncertainty, competitive ratio, makespan, sum of completion times}
}
Document
A Local-Search Algorithm for Steiner Forest
Abstract
In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2-approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995.
We give a local-search-based constant-factor approximation for the problem. Local search brings in new techniques to an area that has for long not seen any improvements and might be a step towards a combinatorial algorithm for the more general survivable network design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Steiner Tree problem, whereas dynamic Steiner Forest is still wide open.
It is easy to see that any constant factor local search algorithm requires steps that add/drop many edges together. We propose natural local moves which, at each step, either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a set of edges to the current solution. This second type of moves is motivated by the potential function we use to measure progress, combining the cost of the solution with a penalty for each connected component. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local minima that arise when using more traditional local moves.
Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to "project" the optimal solution onto the different trees of the local optimum without incurring too much cost (and this argument uses optimality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential function, and our analysis techniques will be useful to develop and analyze local-search algorithms in other contexts.
Cite as
Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, and José Verschae. A Local-Search Algorithm for Steiner Forest. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gro_et_al:LIPIcs.ITCS.2018.31,
author = {Gro{\ss}, Martin and Gupta, Anupam and Kumar, Amit and Matuschke, Jannik and Schmidt, Daniel R. and Schmidt, Melanie and Verschae, Jos\'{e}},
title = {{A Local-Search Algorithm for Steiner Forest}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {31:1--31:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.31},
URN = {urn:nbn:de:0030-drops-83134},
doi = {10.4230/LIPIcs.ITCS.2018.31},
annote = {Keywords: Local Search, Steiner Forest, Approximation Algorithms, Network Design}
}
Document
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
Abstract
Deterministic polynomial-time computation of a representation of a transversal matroid is a longstanding open problem. We present a deterministic computation of a so-called union representation of a transversal matroid in time quasipolynomial in the rank of the matroid. More precisely, we output a collection of linear matroids such that a set is independent in the transversal matroid if and only if it is independent in at least one of them. Our proof directly implies that if one is interested in preserving independent sets of size at most r, for a given r\in\mathbb{N}, but does not care whether larger independent sets are preserved, then a union representation can be computed deterministically in time quasipolynomial in r. This consequence is of independent interest, and sheds light on the power of union~representation.
Our main result also has applications in Parameterized Complexity. First, it yields a fast computation of representative sets, and due to our relaxation in the context of r, this computation also extends to (standard) truncations. In turn, this computation enables to efficiently solve various problems, such as subcases of subgraph isomorphism, motif search and packing problems, in the presence of color lists. Such problems have been studied to model scenarios where pairs of elements to be matched may not be identical but only similar, and color lists aim to describe the set of compatible elements associated with each element.
Cite as
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{lokshtanov_et_al:LIPIcs.ITCS.2018.32,
author = {Lokshtanov, Daniel and Misra, Pranabendu and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
title = {{Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {32:1--32:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.32},
URN = {urn:nbn:de:0030-drops-83144},
doi = {10.4230/LIPIcs.ITCS.2018.32},
annote = {Keywords: travserval matroid, matroid representation, union representation, representative set}
}
Document
Selection Problems in the Presence of Implicit Bias
Abstract
Over the past two decades, the notion of implicit bias has come to serve as an important com- ponent in our understanding of bias and discrimination in activities such as hiring, promotion, and school admissions. Research on implicit bias posits that when people evaluate others - for example, in a hiring context - their unconscious biases about membership in particular demo- graphic groups can have an effect on their decision-making, even when they have no deliberate intention to discriminate against members of these groups. A growing body of experimental work has demonstrated the effect that implicit bias can have in producing adverse outcomes.
Here we propose a theoretical model for studying the effects of implicit bias on selection decisions, and a way of analyzing possible procedural remedies for implicit bias within this model. A canonical situation represented by our model is a hiring setting, in which recruiters are trying to evaluate the future potential of job applicants, but their estimates of potential are skewed by an unconscious bias against members of one group. In this model, we show that measures such as the Rooney Rule, a requirement that at least one member of an underrepresented group be selected, can not only improve the representation of the affected group, but also lead to higher payoffs in absolute terms for the organization performing the recruiting. However, identifying the conditions under which such measures can lead to improved payoffs involves subtle trade- offs between the extent of the bias and the underlying distribution of applicant characteristics, leading to novel theoretical questions about order statistics in the presence of probabilistic side information.
Cite as
Jon Kleinberg and Manish Raghavan. Selection Problems in the Presence of Implicit Bias. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kleinberg_et_al:LIPIcs.ITCS.2018.33,
author = {Kleinberg, Jon and Raghavan, Manish},
title = {{Selection Problems in the Presence of Implicit Bias}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.33},
URN = {urn:nbn:de:0030-drops-83234},
doi = {10.4230/LIPIcs.ITCS.2018.33},
annote = {Keywords: algorithmic fairness, power laws, order statistics, implicit bias, Rooney Rule}
}
Document
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
Abstract
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity
(conditional polynomial lower bounds). Specifically, we aim to answer why sparse graph problems are so hard, and why the Longest Common Subsequence problem gets a savings of a factor of the size of cache times the length of a cache line, but no more. We take the reductions and techniques from complexity and fine-grained complexity and apply them to the I/O model to generate new (conditional) lower bounds as well as new faster algorithms. We also prove the existence of a time hierarchy for the I/O model, which motivates the fine-grained reductions.
- Using fine-grained reductions, we give an algorithm for distinguishing 2 vs. 3 diameter and radius that runs in O(|E|^2/(MB)) cache misses, which for sparse graphs improves over the previous O(|V|^2/B) running time.
- We give new reductions from radius and diameter to Wiener index and median. These reductions are new in both the RAM and I/O models.
- We show meaningful reductions between problems that have linear-time solutions in the RAM model. The reductions use low I/O complexity (typically O(n/B)), and thus help to finely capture between "I/O linear time" O(n/B) and RAM linear time O(n).
- We generate new I/O assumptions based on the difficulty of improving sparse graph problem running times in the I/O model. We create conjectures that the current best known algorithms for Single Source Shortest Paths (SSSP), diameter, and radius are optimal.
- From these I/O-model assumptions, we show that many of the known reductions in the word-RAM model can naturally extend to hold in the I/O model as well (e.g., a lower bound on the I/O complexity of Longest Common Subsequence that matches the best known running time).
- We prove an analog of the Time Hierarchy Theorem in the I/O model, further motivating the study of fine-grained algorithmic differences.
Cite as
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{demaine_et_al:LIPIcs.ITCS.2018.34,
author = {Demaine, Erik D. and Lincoln, Andrea and Liu, Quanquan C. and Lynch, Jayson and Vassilevska Williams, Virginia},
title = {{Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {34:1--34:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.34},
URN = {urn:nbn:de:0030-drops-83335},
doi = {10.4230/LIPIcs.ITCS.2018.34},
annote = {Keywords: IO model, Fine-grained Complexity, Algorithms}
}
Document
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
Abstract
The Longest Common Subsequence (LCS) is one of the most basic similarity measures and it captures important applications in bioinformatics and text analysis. Following the SETH-based nearly-quadratic time lower bounds for LCS from recent years, it is a major open problem to understand the complexity of approximate LCS.
In the last ITCS [AB17] drew an interesting connection between this problem and the area of circuit complexity:
they proved that approximation algorithms for LCS in deterministic truly-subquadratic time imply new circuit lower bounds (E^NP does not have non-uniform linear-size Valiant Series Parallel circuits).
In this work, we strengthen this connection between approximate LCS and circuit complexity by applying the Distributed PCP framework of [ARW17].
We obtain a reduction that holds against much larger approximation factors (super-constant versus 1+o(1)), yields a lower bound for a larger class of circuits (linear-size NC^1), and is also easier to analyze.
Cite as
Amir Abboud and Aviad Rubinstein. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{abboud_et_al:LIPIcs.ITCS.2018.35,
author = {Abboud, Amir and Rubinstein, Aviad},
title = {{Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.35},
URN = {urn:nbn:de:0030-drops-83490},
doi = {10.4230/LIPIcs.ITCS.2018.35},
annote = {Keywords: Distributed PCP, Longest Common Subsequence, Fine-grained Complexity, Strong Exponential Time Hypothesis}
}
Document
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Abstract
We study 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph G = (V,E), an alphabet set Sigma and, for each edge {u, v}, a constraint C_uv, the goal is to find an assignment sigma from V to Sigma that satisfies as many constraints as possible, where a constraint C_uv is said to be satisfied by sigma if C_uv contains (sigma(u),sigma(v)).
While the approximability of 2-CSPs is quite well understood when the alphabet size |Sigma| is constant (see e.g. [37]), many problems are still open when |Sigma| becomes super constant. One open problem that has received significant attention in the literature is whether it is hard to approximate 2-CSPs to within a polynomial factor of both |Sigma| and |V| (i.e. (|Sigma||V|)^Omega(1) factor). As a special case of the so-called Sliding Scale Conjecture, Bellare et al. [5] suggested that the answer to this question might be positive. Alas, despite many efforts by researchers to resolve this conjecture (e.g. [39, 4, 20, 21, 35]), it still remains open to this day.
In this work, we separate |V| and |Sigma| and ask a closely related but weaker question: is it hard to approximate 2-CSPs to within a polynomial factor of |V| (while |Sigma| may be super-polynomial in |Sigma|)? Assuming the exponential time hypothesis (ETH), we answer this question positively: unless ETH fails, no polynomial time algorithm can approximate 2-CSPs to within a factor of |V|^{1-o(1)}. Note that our ratio is not only polynomial but also almost linear. This is almost optimal since a trivial algorithm yields an O(|V|)-approximation for 2-CSPs.
Thanks to a known reduction [25, 16] from 2-CSPs to the Directed Steiner Network (DSN) problem, our result implies an inapproximability result for the latter with polynomial ratio in terms of the number of demand pairs. Specifically, assuming ETH, no polynomial time algorithm can approximate DSN to within a factor of k^{1/4 - o(1)} where k is the number of demand pairs. The ratio is roughly the square root of the approximation ratios achieved by best known polynomial time algorithms [15, 26], which yield O(k^{1/2 + epsilon})-approximation for every constant epsilon > 0.
Additionally, under Gap-ETH, our reduction for 2-CSPs not only rules out polynomial time algorithms, but also fixed parameter tractable (FPT) algorithms parameterized by the number of variables |V|. These are algorithms with running time g(|V|)·|Sigma|^O(1) for some function g. Similar improvements apply for DSN parameterized by the number of demand pairs k.
Cite as
Irit Dinur and Pasin Manurangsi. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dinur_et_al:LIPIcs.ITCS.2018.36,
author = {Dinur, Irit and Manurangsi, Pasin},
title = {{ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {36:1--36:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.36},
URN = {urn:nbn:de:0030-drops-83670},
doi = {10.4230/LIPIcs.ITCS.2018.36},
annote = {Keywords: Hardness of Approximation, Constraint Satisfaction Problems, Directed Steiner Network, Parameterized Complexity}
}
Document
Towards a Unified Complexity Theory of Total Functions
Abstract
The class TFNP, of NP search problems where all instances have solutions, appears not to have complete problems. However, TFNP contains various syntactic subclasses and important problems. We introduce a syntactic class of problems that contains these known subclasses, for the purpose of understanding and classifying TFNP problems. This class is defined in terms of the search for an error in a concisely-represented formal proof. Finally, the known complexity subclasses are based on existence theorems that hold for finite structures; from Herbrand's Theorem, we note that such theorems must apply specifically to finite structures, and not infinite ones.
Cite as
Paul W. Goldberg and Christos H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2018.37,
author = {Goldberg, Paul W. and Papadimitriou, Christos H.},
title = {{Towards a Unified Complexity Theory of Total Functions}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {37:1--37:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.37},
URN = {urn:nbn:de:0030-drops-83403},
doi = {10.4230/LIPIcs.ITCS.2018.37},
annote = {Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP}
}
Document
Edge Estimation with Independent Set Oracles
Abstract
We study the problem of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an n-vertex graph: one that uses only polylog(n) bipartite independent set queries, and another one that uses n^{2/3} polylog(n) independent set queries.
Cite as
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{beame_et_al:LIPIcs.ITCS.2018.38,
author = {Beame, Paul and Har-Peled, Sariel and Natarajan Ramamoorthy, Sivaramakrishnan and Rashtchian, Cyrus and Sinha, Makrand},
title = {{Edge Estimation with Independent Set Oracles}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {38:1--38:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.38},
URN = {urn:nbn:de:0030-drops-83552},
doi = {10.4230/LIPIcs.ITCS.2018.38},
annote = {Keywords: Approximate Counting, Independent Set Queries, Sparsification, Importance Sampling}
}
Document
Computing Exact Minimum Cuts Without Knowing the Graph
Abstract
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem:
on query S \subset V, the oracle returns the size of the cut between S and V \ S.
We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while learning the graph requires ~{\Theta}(n^2) queries).
Cite as
Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2018.39,
author = {Rubinstein, Aviad and Schramm, Tselil and Weinberg, S. Matthew},
title = {{Computing Exact Minimum Cuts Without Knowing the Graph}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {39:1--39:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.39},
URN = {urn:nbn:de:0030-drops-83168},
doi = {10.4230/LIPIcs.ITCS.2018.39},
annote = {Keywords: query complexity, minimum cut}
}
Document
Approximate Clustering with Same-Cluster Queries
Abstract
Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind "do two given points belong to the same optimal cluster?", where the answers to these queries are assumed to be consistent with a unique optimal solution. There are many clustering contexts where such same cluster queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of the k-means clustering problem, with additional margin assumption, can be solved efficiently if one is allowed to make O(k^2 log{k} + k log{n}) same-cluster queries. This is interesting since the k-means problem, even with the margin assumption, is NP-hard.
In this paper, we extend the work of Ashtiani et al. to the approximation setting by showing that a few of such same-cluster queries enables one to get a polynomial-time (1+eps)-approximation algorithm for the k-means problem without any margin assumption on the input dataset. Again, this is interesting since the k-means problem is NP-hard to approximate within a factor (1+c) for a fixed constant 0 < c < 1. The number of same-cluster queries used by the algorithm is poly(k/eps) which is independent of the size n of the dataset. Our algorithm is based on the D^2-sampling technique, also known as the k-means++ seeding algorithm. We also give a conditional lower bound on the number of same-cluster queries showing that if the Exponential Time Hypothesis (ETH) holds, then any such efficient query algorithm needs to make Omega (k/poly log k) same-cluster queries. Our algorithm can be extended for the case where the query answers are wrong with some bounded probability. Another result we show for the k-means++ seeding is that a small modification of the k-means++ seeding within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known O(log k)-approximation algorithm.
Cite as
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate Clustering with Same-Cluster Queries. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 40:1-40:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{ailon_et_al:LIPIcs.ITCS.2018.40,
author = {Ailon, Nir and Bhattacharya, Anup and Jaiswal, Ragesh and Kumar, Amit},
title = {{Approximate Clustering with Same-Cluster Queries}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {40:1--40:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.40},
URN = {urn:nbn:de:0030-drops-83358},
doi = {10.4230/LIPIcs.ITCS.2018.40},
annote = {Keywords: k-means, semi-supervised learning, query bounds}
}
Document
Graph Clustering using Effective Resistance
Abstract
We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e.
sum(i < j) |E(V(i), V(j)| < w(E)/\delta
and the effective resistance diameter of each of the induced subgraphs
G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e.
max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E)
for all i = 1,..., h. In particular, it is possible to remove one
percent of weight of edges of any given graph such that each of the
resulting connected components has effective resistance diameter at
most the inverse of the average weighted degree. Our proof is based
on a new connection between effective resistance and low conductance
sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Cite as
Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{alev_et_al:LIPIcs.ITCS.2018.41,
author = {Alev, Vedat Levi and Anari, Nima and Lau, Lap Chi and Oveis Gharan, Shayan},
title = {{Graph Clustering using Effective Resistance}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {41:1--41:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.41},
URN = {urn:nbn:de:0030-drops-83696},
doi = {10.4230/LIPIcs.ITCS.2018.41},
annote = {Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning}
}
Document
Lattice-based Locality Sensitive Hashing is Optimal
Abstract
Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (STOC'98) to give the first sublinear time algorithm for the c-approximate nearest neighbor (ANN) problem using only polynomial space. At a high level, an LSH family hashes "nearby" points to the same bucket and "far away" points to different buckets. The quality of measure of an LSH family is its LSH exponent, which helps determine both query time and space usage.
In a seminal work, Andoni and Indyk (FOCS '06) constructed an LSH family based on random ball partitionings of space that achieves an LSH exponent of 1/c^2 for the l_2 norm, which was later shown to be optimal by Motwani, Naor and Panigrahy (SIDMA '07) and O'Donnell, Wu and Zhou (TOCT '14). Although optimal in the LSH exponent, the ball partitioning approach is computationally expensive. So, in the same work, Andoni and Indyk proposed a simpler and more practical hashing scheme based on Euclidean lattices and provided computational results using the 24-dimensional Leech lattice. However, no theoretical analysis of the scheme was given, thus leaving open the question of finding the exponent of lattice based LSH.
In this work, we resolve this question by showing the existence of lattices achieving the optimal LSH exponent of 1/c^2 using techniques from the geometry of numbers. At a more conceptual level, our results show that optimal LSH space partitions can have periodic structure. Understanding the extent to which additional structure can be imposed on these partitions, e.g. to yield low space and query complexity, remains an important open problem.
Cite as
Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, and Elena Grigorescu. Lattice-based Locality Sensitive Hashing is Optimal. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chandrasekaran_et_al:LIPIcs.ITCS.2018.42,
author = {Chandrasekaran, Karthekeyan and Dadush, Daniel and Gandikota, Venkata and Grigorescu, Elena},
title = {{Lattice-based Locality Sensitive Hashing is Optimal}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {42:1--42:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.42},
URN = {urn:nbn:de:0030-drops-83470},
doi = {10.4230/LIPIcs.ITCS.2018.42},
annote = {Keywords: Locality Sensitive Hashing, Approximate Nearest Neighbor Search, Random Lattices}
}
Document
Differential Privacy on Finite Computers
Abstract
We consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomial-time algorithms. We use a case study: the basic problem of approximating the histogram of a categorical dataset over a possibly large data universe X. The classic Laplace Mechanism (Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy & Confidentiality 2017) does not satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP 2012), take time at least linear in |X|, which can be exponential in the bit length of the input.
In this paper, we provide strict polynomial-time discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy guarantee. One of our algorithms produces a sparse histogram as output. Its "per-bin accuracy" (the error on individual bins) is worse than that of the Laplace Mechanism by a factor of log |X|, but we prove a lower bound showing that this is necessary for any algorithm that produces a sparse histogram. A second algorithm avoids this lower bound, and matches the per-bin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable representation of a dense histogram; it is based on an (n+1)-wise independent implementation of an appropriately clamped version of the Discrete Geometric Mechanism.
Cite as
Victor Balcer and Salil Vadhan. Differential Privacy on Finite Computers. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{balcer_et_al:LIPIcs.ITCS.2018.43,
author = {Balcer, Victor and Vadhan, Salil},
title = {{Differential Privacy on Finite Computers}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {43:1--43:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.43},
URN = {urn:nbn:de:0030-drops-83537},
doi = {10.4230/LIPIcs.ITCS.2018.43},
annote = {Keywords: Algorithms, Differential Privacy, Discrete Computation, Histograms}
}
Document
Finite Sample Differentially Private Confidence Intervals
Abstract
We study the problem of estimating finite sample confidence intervals of the mean of a normal population under the constraint of differential privacy. We consider both the known and unknown variance cases and construct differentially private algorithms to estimate confidence intervals. Crucially, our algorithms guarantee a finite sample coverage, as opposed to an asymptotic coverage. Unlike most previous differentially private algorithms, we do not require the domain of the samples to be bounded. We also prove lower bounds on the expected size of any differentially private confidence set showing that our the parameters are optimal up to polylogarithmic factors.
Cite as
Vishesh Karwa and Salil Vadhan. Finite Sample Differentially Private Confidence Intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 44:1-44:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{karwa_et_al:LIPIcs.ITCS.2018.44,
author = {Karwa, Vishesh and Vadhan, Salil},
title = {{Finite Sample Differentially Private Confidence Intervals}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {44:1--44:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.44},
URN = {urn:nbn:de:0030-drops-83449},
doi = {10.4230/LIPIcs.ITCS.2018.44},
annote = {Keywords: Differential Privacy, Confidence Intervals, Lower bounds, Finite Sample}
}
Document
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Abstract
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a large fraction of arbitrary additional data. Resilience is a weaker condition than most other properties considered so far in the literature, and yet enables robust estimation in a broader variety of settings. We provide new information-theoretic results on robust distribution learning, robust estimation of stochastic block models, and robust mean estimation under bounded kth moments. We also provide new algorithmic results on robust distribution learning, as well as robust mean estimation in p-norms. Among our proof techniques is a method for pruning a high-dimensional distribution with bounded 1st moments to a stable "core" with bounded 2nd moments, which may be of independent interest.
Cite as
Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{steinhardt_et_al:LIPIcs.ITCS.2018.45,
author = {Steinhardt, Jacob and Charikar, Moses and Valiant, Gregory},
title = {{Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {45:1--45:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.45},
URN = {urn:nbn:de:0030-drops-83687},
doi = {10.4230/LIPIcs.ITCS.2018.45},
annote = {Keywords: robust learning, outliers, stochastic block models, p-norm estimation}
}
Document
Recovering Structured Probability Matrices
Abstract
We consider the problem of accurately recovering a matrix B of size M by M, which represents a probability distribution over M^2 outcomes, given access to an observed matrix of "counts" generated by taking independent samples from the distribution B. How can structural properties of the underlying matrix B be leveraged to yield computationally efficient and information theoretically optimal reconstruction algorithms? When can accurate reconstruction be accomplished in the sparse data regime? This basic problem lies at the core of a number of questions that are currently being considered by different communities, including building recommendation systems and collaborative filtering in the sparse data regime, community detection in sparse random graphs, learning structured models such as topic models or hidden Markov models, and the efforts from the natural language processing community to compute "word embeddings". Many aspects of this problem---both in terms of learning and property testing/estimation and on both the algorithmic and information theoretic sides---remain open.
Our results apply to the setting where B has a low rank structure. For this setting, we propose an efficient (and practically viable) algorithm that accurately recovers the underlying M by M matrix using O(M) samples} (where we assume the rank is a constant). This linear sample complexity is optimal, up to constant factors, in an extremely strong sense: even testing basic properties of the underlying matrix (such as whether it has rank 1 or 2) requires Omega(M) samples. Additionally, we provide an even stronger lower bound showing that distinguishing whether a sequence of observations were drawn from the uniform distribution over M observations versus being generated by a well-conditioned Hidden Markov Model with two hidden states requires Omega(M) observations, while our positive results for recovering B immediately imply that Omega(M) observations suffice to learn such an HMM. This lower bound precludes sublinear-sample hypothesis tests for basic properties, such as identity or uniformity, as well as sublinear sample estimators for quantities such as the entropy rate of HMMs.
Cite as
Qingqing Huang, Sham M. Kakade, Weihao Kong, and Gregory Valiant. Recovering Structured Probability Matrices. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{huang_et_al:LIPIcs.ITCS.2018.46,
author = {Huang, Qingqing and Kakade, Sham M. and Kong, Weihao and Valiant, Gregory},
title = {{Recovering Structured Probability Matrices}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.46},
URN = {urn:nbn:de:0030-drops-83625},
doi = {10.4230/LIPIcs.ITCS.2018.46},
annote = {Keywords: Random matrices, matrix recovery, stochastic block model, Hidden Markov Models}
}
Document
Learning Discrete Distributions from Untrusted Batches
Abstract
We consider the problem of learning a discrete distribution in the presence of an epsilon fraction of malicious data sources. Specifically, we consider the setting where there is some underlying distribution, p, and each data source provides a batch of >= k samples, with the guarantee that at least a (1 - epsilon) fraction of the sources draw their samples from a distribution with total variation distance at most \eta from p. We make no assumptions on the data provided by the remaining epsilon fraction of sources--this data can even be chosen as an adversarial function of the (1 - epsilon) fraction of "good" batches. We provide two algorithms: one with runtime exponential in the support size, n, but polynomial in k, 1/epsilon and 1/eta that takes O((n + k)/epsilon^2) batches and recovers p to error O(eta + epsilon/sqrt(k)). This recovery accuracy is information theoretically optimal, to constant factors, even given an infinite number of data sources. Our second algorithm applies to the eta = 0 setting and also achieves an O(epsilon/sqrt(k)) recover guarantee, though it runs in poly((nk)^k) time. This second algorithm, which approximates a certain tensor via a rank-1 tensor minimizing l_1 distance, is surprising in light of the hardness of many low-rank tensor approximation problems, and may be of independent interest.
Cite as
Mingda Qiao and Gregory Valiant. Learning Discrete Distributions from Untrusted Batches. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{qiao_et_al:LIPIcs.ITCS.2018.47,
author = {Qiao, Mingda and Valiant, Gregory},
title = {{Learning Discrete Distributions from Untrusted Batches}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {47:1--47:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.47},
URN = {urn:nbn:de:0030-drops-83215},
doi = {10.4230/LIPIcs.ITCS.2018.47},
annote = {Keywords: robust statistics, information-theoretic optimality}
}
Document
Competing Bandits: Learning Under Competition
Abstract
Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition--how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems.
In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen. We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the "competition vs. innovation" relationship, a well-studied theme in economics.
Cite as
Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu. Competing Bandits: Learning Under Competition. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 48:1-48:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{mansour_et_al:LIPIcs.ITCS.2018.48,
author = {Mansour, Yishay and Slivkins, Aleksandrs and Wu, Zhiwei Steven},
title = {{Competing Bandits: Learning Under Competition}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {48:1--48:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.48},
URN = {urn:nbn:de:0030-drops-83341},
doi = {10.4230/LIPIcs.ITCS.2018.48},
annote = {Keywords: machine learning, game theory, competition, exploration, rationality}
}
Document
Limits for Rumor Spreading in Stochastic Populations
Abstract
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population.
In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise.
We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis Niger desert ants.
Cite as
Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale. Limits for Rumor Spreading in Stochastic Populations. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{boczkowski_et_al:LIPIcs.ITCS.2018.49,
author = {Boczkowski, Lucas and Feinerman, Ofer and Korman, Amos and Natale, Emanuele},
title = {{Limits for Rumor Spreading in Stochastic Populations}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {49:1--49:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.49},
URN = {urn:nbn:de:0030-drops-83207},
doi = {10.4230/LIPIcs.ITCS.2018.49},
annote = {Keywords: Noisy communication, Passive communication, Ant recruitment, Hypothesis testing}
}
Document
Making Asynchronous Distributed Computations Robust to Channel Noise
Abstract
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages.
Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.
Cite as
Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. Making Asynchronous Distributed Computations Robust to Channel Noise. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2018.50,
author = {Censor-Hillel, Keren and Gelles, Ran and Haeupler, Bernhard},
title = {{Making Asynchronous Distributed Computations Robust to Channel Noise}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {50:1--50:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.50},
URN = {urn:nbn:de:0030-drops-83184},
doi = {10.4230/LIPIcs.ITCS.2018.50},
annote = {Keywords: Distributed Computation, Coding for Interactive Communication, Noise- Resilient Computation, Coding Theory}
}
Document
Distance-Preserving Graph Contractions
Abstract
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs.
In this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible.
Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance d, the corresponding super-vertices remain at distance at least \varphi(d) in the contracted graph, where \varphi is a tolerance function bounding the permitted distance distortion.
We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions \varphi(x)=x/\alpha-\beta, where \alpha \geq 1 and \beta \geq 0 are arbitrary real-valued parameters.
Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases.
Further we analyze the asymptotic behavior of the size of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.
Cite as
Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, and Frieder Smolny. Distance-Preserving Graph Contractions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bernstein_et_al:LIPIcs.ITCS.2018.51,
author = {Bernstein, Aaron and D\"{a}ubel, Karl and Disser, Yann and Klimm, Max and M\"{u}tze, Torsten and Smolny, Frieder},
title = {{Distance-Preserving Graph Contractions}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.51},
URN = {urn:nbn:de:0030-drops-83427},
doi = {10.4230/LIPIcs.ITCS.2018.51},
annote = {Keywords: distance oracle, contraction, spanner}
}
Document
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
Abstract
In graph sparsification, the goal has almost always been of global nature: compress a graph into a smaller subgraph (sparsifier) that maintains certain features of the original graph.
Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory.
This paper studies sparsifiers that have bounded (maximum) degree, and are thus locally sparse, aiming to improve local measures of runtime and memory. To improve those local measures, it is important to be able to compute such sparsifiers locally.
We initiate the study of local algorithms for bounded degree sparsifiers in unweighted sparse graphs, focusing on the problems of vertex cover, matching, and independent set. Let \eps > 0 be a slack parameter and \alpha \ge 1 be a density parameter.
We devise local algorithms for computing:
1. A (1+\eps)-vertex cover sparsifier of degree O(\alpha / \eps), for any graph of arboricity \alpha.\footnote{In a graph of arboricity \alpha the average degree of any induced subgraph is at most 2\alpha.}
2. A (1+\eps)-maximum matching sparsifier and also a (1+\eps)-maximal matching sparsifier of degree O(\alpha / \eps, for any graph of arboricity \alpha.
3. A (1+\eps)-independent set sparsifier of degree O(\alpha^2 / \eps), for any graph of average degree \alpha.
Our algorithms require only a single communication round in the standard message passing model of distributed computing,
and moreover, they can be simulated locally in a trivial way.
As an immediate application we can extend results from distributed computing and local computation algorithms that apply to graphs of degree bounded by d to graphs of arboricity O(d / \eps) or average degree O(d^2 / \eps), at the expense of increasing the approximation guarantee by a factor of (1+\eps). In particular, we can extend the plethora of recent local computation algorithms for approximate maximum and maximal matching from bounded degree graphs to bounded arboricity graphs with a negligible loss in the approximation guarantee.
The inherently local behavior of our algorithms can be used to amplify the approximation guarantee of any sparsifier in time roughly linear in its size,
which has immediate applications in the area of dynamic graph algorithms. In particular, the state-of-the-art algorithm for
maintaining (2-\eps)-vertex cover (VC) is at least linear in the graph size, even in dynamic forests. We provide a reduction from the dynamic to the static case, showing that if a t-VC can be computed from scratch in time T(n) in any (sub)family of graphs with arboricity bounded by \alpha, for an arbitrary t \ge 1,
then a (t+\eps)-VC can be maintained with update time \frac{T(n)}{O((n / \alpha) \cdot \eps^2)}, for any \eps > 0. For planar graphs this yields an algorithm for maintaining a (1+\eps)-VC with constant update time for any constant \eps > 0.
Cite as
Shay Solomon. Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{solomon:LIPIcs.ITCS.2018.52,
author = {Solomon, Shay},
title = {{Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {52:1--52:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.52},
URN = {urn:nbn:de:0030-drops-83647},
doi = {10.4230/LIPIcs.ITCS.2018.52},
annote = {Keywords: arboricity, bounded degree, local algorithm, sparsifier}
}
Document
Proofs of Proximity for Distribution Testing
Abstract
Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large number of samples to test, which motivates the question of whether there are natural settings wherein fewer samples suffice.
We initiate a study of proofs of proximity for properties of distributions. In their basic form, these proof systems consist of a tester that not only has sample access to a distribution but also explicit access to a proof string that depends on the distribution. We refer to these as NP distribution testers, or MA distribution testers if the tester is a probabilistic algorithm. We also study the more general notion of IP distribution testers, in which the tester interacts with an all-powerful untrusted prover.
We investigate the power and limitations of proofs of proximity for distributions and chart a landscape that, surprisingly, is significantly different from that of proofs of proximity for functions. Our main results include showing that MA distribution testers can be quadratically stronger than standard distribution testers, but no stronger than that; in contrast, IP distribution testers can be exponentially stronger than standard distribution testers, but when restricted to public coins they can be at best quadratically stronger.
Cite as
Alessandro Chiesa and Tom Gur. Proofs of Proximity for Distribution Testing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2018.53,
author = {Chiesa, Alessandro and Gur, Tom},
title = {{Proofs of Proximity for Distribution Testing}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {53:1--53:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.53},
URN = {urn:nbn:de:0030-drops-83114},
doi = {10.4230/LIPIcs.ITCS.2018.53},
annote = {Keywords: distribution testing, proofs of proximity, property testing}
}
Document
Efficient Testing without Efficient Regularity
Abstract
The regularity lemma of Szemeredi turned out to be the most powerful tool for studying the testability of graph properties in the dense graph model. In fact, as we argue in this paper, this lemma can be used in order to prove (essentially) all the previous results in this area. More precisely, a barrier for obtaining an efficient testing algorithm for a graph property P was having an efficient regularity lemma for graphs satisfying P. The problem is that for many natural graph properties (e.g. triangle freeness) it is known that a graph can satisfy P and still only have regular partitions of tower-type size. This means that there was no viable path for obtaining reasonable bounds on the query complexity of testing such properties.
In this paper we consider the property of being induced C_4-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type size.
By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for testing this property. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox.
We thus obtain the first example of an efficient testing algorithm that cannot be derived from an efficient version of the regularity lemma.
Cite as
Lior Gishboliner and Asaf Shapira. Efficient Testing without Efficient Regularity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{gishboliner_et_al:LIPIcs.ITCS.2018.54,
author = {Gishboliner, Lior and Shapira, Asaf},
title = {{Efficient Testing without Efficient Regularity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {54:1--54:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.54},
URN = {urn:nbn:de:0030-drops-83124},
doi = {10.4230/LIPIcs.ITCS.2018.54},
annote = {Keywords: Property testing, Induced C\underline4-freeness}
}
Document
Improper Learning by Refuting
Abstract
The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of efficient agnostic learning.
We introduce refutation complexity, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of efficient agnostic learning. Informally, refutation complexity of a class C is the minimum number of example-label pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of C (structure) and the case where the labels are i.i.d. Rademacher random variables (noise). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and co-authors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence.
In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.
Cite as
Pravesh K. Kothari and Roi Livni. Improper Learning by Refuting. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 55:1-55:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kothari_et_al:LIPIcs.ITCS.2018.55,
author = {Kothari, Pravesh K. and Livni, Roi},
title = {{Improper Learning by Refuting}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {55:1--55:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.55},
URN = {urn:nbn:de:0030-drops-83488},
doi = {10.4230/LIPIcs.ITCS.2018.55},
annote = {Keywords: learning thoery, computation learning}
}
Document
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
Abstract
In computational complexity, a complexity class is given by a set of problems or functions, and a basic challenge is to show separations of complexity classes A != B especially when A is known to be a subset of B. In this paper we introduce a homological theory of functions that can be used to establish complexity separations, while also providing other interesting consequences.
We propose to associate a topological space S_A to each class of functions A, such that,
to separate complexity classes A from a superclass B', it suffices to observe a change in "the number of holes", i.e. homology, in S_A as a subclass B of B' is added to A. In other words, if the homologies of S_A and S_{A union B} are different, then A != B'.
We develop the underlying theory of functions based on homological commutative algebra and Stanley-Reisner theory, and prove a "maximal principle" for polynomial threshold functions that is used to recover Aspnes, Beigel, Furst, and Rudich's characterization of the polynomial threshold degree of symmetric functions.
A surprising coincidence is demonstrated, where, roughly speaking, the maximal dimension of "holes" in S_A upper bounds the VC dimension of A, with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals over the finite field of 2 elements, or common algebraic cases such as when the Stanley-Reisner ring of S_A is Cohen-Macaulay. As another interesting application of our theory, we prove a result that a priori has nothing to do with complexity separation: it characterizes when a vector subspace intersects the positive cone, in terms of homological conditions. By analogy to Farkas' result doing the same with linear conditions, we call our theorem the Homological Farkas Lemma.
Cite as
Greg Yang. A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{yang:LIPIcs.ITCS.2018.56,
author = {Yang, Greg},
title = {{A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {56:1--56:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.56},
URN = {urn:nbn:de:0030-drops-83436},
doi = {10.4230/LIPIcs.ITCS.2018.56},
annote = {Keywords: Homology, Stanley-Reisner, Cellular resolution, VC dimension, Homological Farkas}
}
Document
Long Term Memory and the Densest K-Subgraph Problem
Abstract
In a recent experiment, a cell in the human medial temporal lobe (MTL) encoding one sensory stimulus starts to also respond to a second stimulus following a combined experience associating the two. We develop a theoretical model predicting that an assembly of cells with exceptionally high synaptic intraconnectivity can emerge, in response to a particular sensory experience, to encode and abstract that experience. We also show that two such assemblies are modified to increase their intersection after a sensory event that associates the two corresponding stimuli. The main technical tools employed are random graph theory, and Bernoulli approximations. Assembly creation must overcome a computational challenge akin to the Densest K-Subgraph problem, namely selecting, from a large population of randomly and sparsely interconnected cells, a subset with exceptionally high density of interconnections. We identify three mechanisms that help achieve this feat in our model: (1) a simple two-stage randomized algorithm, and (2) the "triangle completion bias" in synaptic connectivity and a "birthday paradox", while (3) the strength of these connections is enhanced through Hebbian plasticity.
Cite as
Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala. Long Term Memory and the Densest K-Subgraph Problem. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{legenstein_et_al:LIPIcs.ITCS.2018.57,
author = {Legenstein, Robert and Maass, Wolfgang and Papadimitriou, Christos H. and Vempala, Santosh S.},
title = {{Long Term Memory and the Densest K-Subgraph Problem}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {57:1--57:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.57},
URN = {urn:nbn:de:0030-drops-83593},
doi = {10.4230/LIPIcs.ITCS.2018.57},
annote = {Keywords: Brain computation, long term memory, assemblies, association}
}
Document
Toward a Theory of Markov Influence Systems and their Renormalization
Abstract
Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems" (MIS), the transition probabilities of the chains change as a function of the current state distribution. This work introduces a renormalization framework for analyzing the dynamics of MIS. It comes in two independent parts: first, we generalize the standard classification of Markov chain states to the dynamic case by showing how to "parse" graph sequences. We then use this framework to
carry out the bifurcation analysis of a few important MIS families.
In particular, we show that irreducible MIS are almost always
asymptotically periodic. We also give an example of "hyper-torpid" mixing, where a stationary distribution is reached in super-exponential time, a timescale that cannot be achieved by any Markov chain.
Cite as
Bernard Chazelle. Toward a Theory of Markov Influence Systems and their Renormalization. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chazelle:LIPIcs.ITCS.2018.58,
author = {Chazelle, Bernard},
title = {{Toward a Theory of Markov Influence Systems and their Renormalization}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {58:1--58:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.58},
URN = {urn:nbn:de:0030-drops-83317},
doi = {10.4230/LIPIcs.ITCS.2018.58},
annote = {Keywords: Markov influence systems, nonlinear Markov chains, dynamical systems, renormalization, graph sequence parsing}
}
Document
Learning Dynamics and the Co-Evolution of Competing Sexual Species
Abstract
We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model [Livnat et al. FOCS'14] the fitness of an individual depends on whether the truth assignments on n variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is periodic. These cycles stay bounded away from the boundary and thus, learning-dynamics competition between sexual species can provide an explanation for genetic diversity. This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked.
The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition.
Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.
Cite as
Georgios Piliouras and Leonard J. Schulman. Learning Dynamics and the Co-Evolution of Competing Sexual Species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{piliouras_et_al:LIPIcs.ITCS.2018.59,
author = {Piliouras, Georgios and Schulman, Leonard J.},
title = {{Learning Dynamics and the Co-Evolution of Competing Sexual Species}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {59:1--59:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Karlin, Anna R.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.59},
URN = {urn:nbn:de:0030-drops-83637},
doi = {10.4230/LIPIcs.ITCS.2018.59},
annote = {Keywords: Dynamical Systems, Potential Game, Team Zero-Sum Game, Boolean Functions, Replicator Dynamics}
}