5 Search Results for "Kane, Daniel M."

Document
DOI: 10.4230/LIPIcs.STACS.2024.25
Depth-3 Circuit Lower Bounds for k-OV

Authors: Tameem Choudhury and Karteek Sreenivasaiah

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples A and B of n Boolean vectors, each of dimension d, decide if there exist vectors u ∈ A, and v ∈ B, such that u and v are orthogonal. This problem, and its generalization k-OV defined analogously for k tuples, are central problems in the area of fine-grained complexity. One of the major conjectures in fine-grained complexity is that k-OV cannot be solved by a randomised algorithm in n^{k-ε}poly(d) time for any constant ε > 0. In this paper, we are interested in unconditional lower bounds against k-OV, but for weaker models of computation than the general Turing Machine. In particular, we are interested in circuit lower bounds to computing k-OV by Boolean circuit families of depth 3 of the form OR-AND-OR, or equivalently, a disjunction of CNFs. We show that for all k ≤ d, any disjunction of t-CNFs computing k-OV requires size Ω((n/t)^k). In particular, when k is a constant, any disjunction of k-CNFs computing k-OV needs to use Ω(n^k) CNFs. This matches the brute-force construction, and for each fixed k > 2, this is the first unconditional Ω(n^k) lower bound against k-OV for a computation model that can compute it in size O(n^k). Our results partially resolve a conjecture by Kane and Williams [Daniel M. Kane and Richard Ryan Williams, 2019] (page 12, conjecture 10) about depth-3 AC⁰ circuits computing 2-OV. As a secondary result, we show an exponential lower bound on the size of AND∘OR∘AND circuits computing 2-OV when d is very large. Since 2-OV reduces to k-OV by projections trivially, this lower bound works against k-OV as well.
Cite as

Tameem Choudhury and Karteek Sreenivasaiah. Depth-3 Circuit Lower Bounds for k-OV. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{choudhury_et_al:LIPIcs.STACS.2024.25,
  author =	{Choudhury, Tameem and Sreenivasaiah, Karteek},
  title =	{{Depth-3 Circuit Lower Bounds for k-OV}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.25},
  URN =		{urn:nbn:de:0030-drops-197359},
  doi =		{10.4230/LIPIcs.STACS.2024.25},
  annote =	{Keywords: fine grained complexity, k-OV, circuit lower bounds, depth-3 circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.48
The Orthogonal Vectors Conjecture for Branching Programs and Formulas

Authors: Daniel M. Kane and Richard Ryan Williams

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires n^{2-o(1)} time to solve, for all d=omega(log n). Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in P, such as Edit Distance, Frechet Distance, Longest Common Subsequence, and approximating the diameter of a graph. We prove that OVC is true in several computational models of interest: - For all sufficiently large n and d, OV for n vectors in {0,1}^d has branching program complexity Theta~(n * min(n,2^d)). In particular, the lower and upper bounds match up to polylog factors. - OV has Boolean formula complexity Theta~(n * min(n,2^d)), over all complete bases of O(1) fan-in. - OV requires Theta~(n * min(n,2^d)) wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in. Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV. The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the "average case" even for AC^0 formulas: For all p in (0,1) there is a delta_p > 0 such that for every n and d, OV instances with input bits independently set to 1 with probability p (and 0 otherwise) can be solved with AC^0 formulas of O(n^{2-delta_p}) size, on all but a o_n(1) fraction of instances. Moreover, lim_{p - > 1}delta_p = 1.
Cite as

Daniel M. Kane and Richard Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kane_et_al:LIPIcs.ITCS.2019.48,
  author =	{Kane, Daniel M. and Williams, Richard Ryan},
  title =	{{The Orthogonal Vectors Conjecture for Branching Programs and Formulas}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.48},
  URN =		{urn:nbn:de:0030-drops-101418},
  doi =		{10.4230/LIPIcs.ITCS.2019.48},
  annote =	{Keywords: fine-grained complexity, orthogonal vectors, branching programs, symmetric functions, Boolean formulas}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.82
Generalized Comparison Trees for Point-Location Problems

Authors: Daniel M. Kane, Shachar Lovett, and Shay Moran

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Let H be an arbitrary family of hyper-planes in d-dimensions. We show that the point-location problem for H can be solved by a linear decision tree that only uses a special type of queries called generalized comparison queries. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from H; in particular, if all hyperplanes in H are k-sparse then generalized comparisons are 2k-sparse. The depth of the obtained linear decision tree is polynomial in d and logarithmic in |H|, which is comparable to previous results in the literature that use general linear queries. This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017]. The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries. Our analysis combines a seminal result of Forster regarding sets in isotropic position [Forster, JCSS 2002], the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.
Cite as

Daniel M. Kane, Shachar Lovett, and Shay Moran. Generalized Comparison Trees for Point-Location Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kane_et_al:LIPIcs.ICALP.2018.82,
  author =	{Kane, Daniel M. and Lovett, Shachar and Moran, Shay},
  title =	{{Generalized Comparison Trees for Point-Location Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{82:1--82:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.82},
  URN =		{urn:nbn:de:0030-drops-90862},
  doi =		{10.4230/LIPIcs.ICALP.2018.82},
  annote =	{Keywords: linear decision trees, comparison queries, point location problems}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.8
Near-Optimal Closeness Testing of Discrete Histogram Distributions

Authors: Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We investigate the problem of testing the equivalence between two discrete histograms. A k-histogram over [n] is a probability distribution that is piecewise constant over some set of k intervals over [n]. Histograms have been extensively studied in computer science and statistics. Given a set of samples from two k-histogram distributions p, q over [n], we want to distinguish (with high probability) between the cases that p = q and ||p ? q||_1 >= epsilon. The main contribution of this paper is a new algorithm for this testing problem and a nearly matching information-theoretic lower bound. Specifically, the sample complexity of our algorithm matches our lower bound up to a logarithmic factor, improving on previous work by polynomial factors in the relevant parameters. Our algorithmic approach applies in a more general setting and yields improved sample upper bounds for testing closeness of other structured distributions as well.
Cite as

Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Near-Optimal Closeness Testing of Discrete Histogram Distributions. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diakonikolas_et_al:LIPIcs.ICALP.2017.8,
  author =	{Diakonikolas, Ilias and Kane, Daniel M. and Nikishkin, Vladimir},
  title =	{{Near-Optimal Closeness Testing of Discrete Histogram Distributions}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.8},
  URN =		{urn:nbn:de:0030-drops-74937},
  doi =		{10.4230/LIPIcs.ICALP.2017.8},
  annote =	{Keywords: distribution testing, histograms, closeness testing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.567
A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting

Authors: Daniel M. Kane

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
We construct and analyze a new pseudorandom generator for degree 2 polynomial threshold functions with respect to the Gaussian measure. In particular, we obtain one whose seed length is polylogarithmic in both the dimension and the desired error, a substantial improvement over existing constructions. Our generator is obtained as an appropriate weighted average of pseudorandom generators against read once branching programs. The analysis requires a number of ideas including a hybrid argument and a structural result that allows us to treat our degree 2 threshold function as a function of a number of linear polynomials and one approximately linear polynomial.
Cite as

Daniel M. Kane. A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 567-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kane:LIPIcs.CCC.2015.567,
  author =	{Kane, Daniel M.},
  title =	{{A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{567--581},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.567},
  URN =		{urn:nbn:de:0030-drops-50534},
  doi =		{10.4230/LIPIcs.CCC.2015.567},
  annote =	{Keywords: polynomial threshold function, pseudorandom generator, Gaussian distribution}
}
  • Refine by Author
  • 4 Kane, Daniel M.
  • 1 Choudhury, Tameem
  • 1 Diakonikolas, Ilias
  • 1 Lovett, Shachar
  • 1 Moran, Shay
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Circuit complexity
  • 1 Theory of computation
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Boolean formulas
  • 1 Gaussian distribution
  • 1 branching programs
  • 1 circuit lower bounds
  • 1 closeness testing
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017
  • 1 2018
  • 1 2019
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact