33 Search Results for "K�cher, Chris"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.69
Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality

Authors: Ohad Klein, Joseph Slote, Alexander Volberg, and Haonan Zhang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice binom([n],k), the hypergrid [K]ⁿ, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function f over products of the cyclic group {exp(2π i k/K)}_{k = 1}^K controls the supremum of f over the entire polytorus ({z ∈ ℂ:|z| = 1}ⁿ), with multiplicative constant C depending on K and deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., C does not depend on n). This dimension-free Remez-type inequality removes the main technical barrier to giving 𝒪(log n) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-K qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust-Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work [Eskenazis and Ivanisvili, 2022; Huang et al., 2022; Volberg and Zhang, 2023] that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations - a phenomenon that greatly extends the reach of low-degree learning in quantum science [Huang et al., 2022].
Cite as

Ohad Klein, Joseph Slote, Alexander Volberg, and Haonan Zhang. Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.ITCS.2024.69,
  author =	{Klein, Ohad and Slote, Joseph and Volberg, Alexander and Zhang, Haonan},
  title =	{{Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{69:1--69:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.69},
  URN =		{urn:nbn:de:0030-drops-195977},
  doi =		{10.4230/LIPIcs.ITCS.2024.69},
  annote =	{Keywords: Analysis of Boolean Functions, Remez Inequality, Bohnenblust-Hille Inequality, Statistical Learning Theory, Qudits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.92
Parity vs. AC0 with Simple Quantum Preprocessing

Authors: Joseph Slote

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
A recent line of work [Bravyi et al., 2018; Watts et al., 2019; Grier and Schaeffer, 2020; Bravyi et al., 2020; Watts and Parham, 2023] has shown the unconditional advantage of constant-depth quantum computation, or QNC⁰, over NC⁰, AC⁰, and related models of classical computation. Problems exhibiting this advantage include search and sampling tasks related to the parity function, and it is natural to ask whether QNC⁰ can be used to help compute parity itself. Namely, we study AC⁰∘QNC⁰ - a hybrid circuit model where AC⁰ operates on measurement outcomes of a QNC⁰ circuit - and we ask whether Par ∈ AC⁰∘QNC⁰. We believe the answer is negative. In fact, we conjecture AC⁰∘QNC⁰ cannot even achieve Ω(1) correlation with parity. As evidence for this conjecture, we prove: - When the QNC⁰ circuit is ancilla-free, this model can achieve only negligible correlation with parity, even when AC⁰ is replaced with any function having LMN-like decay in its Fourier spectrum. - For the general (non-ancilla-free) case, we show via a connection to nonlocal games that the conjecture holds for any class of postprocessing functions that has approximate degree o(n) and is closed under restrictions. Moreover, this is true even when the QNC⁰ circuit is given arbitrary quantum advice. By known results [Bun et al., 2019], this confirms the conjecture for linear-size AC⁰ circuits. - Another approach to proving the conjecture is to show a switching lemma for AC⁰∘QNC⁰. Towards this goal, we study the effect of quantum preprocessing on the decision tree complexity of Boolean functions. We find that from the point of view of decision tree complexity, nonlocal channels are no better than randomness: a Boolean function f precomposed with an n-party nonlocal channel is together equal to a randomized decision tree with worst-case depth at most DT_depth[f]. Taken together, our results suggest that while QNC⁰ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output, inaccessible to simple classical computation for solving decision problems.
Cite as

Joseph Slote. Parity vs. AC0 with Simple Quantum Preprocessing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 92:1-92:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{slote:LIPIcs.ITCS.2024.92,
  author =	{Slote, Joseph},
  title =	{{Parity vs. AC0 with Simple Quantum Preprocessing}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{92:1--92:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.92},
  URN =		{urn:nbn:de:0030-drops-196209},
  doi =		{10.4230/LIPIcs.ITCS.2024.92},
  annote =	{Keywords: QNC0, AC0, Nonlocal games, k-wise indistinguishability, approximate degree, switching lemma, Fourier concentration}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.15
Regular Separators for VASS Coverability Languages

Authors: Chris Köcher and Georg Zetzsche

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We study regular separators of vector addition systems (VASS, for short) with coverability semantics. A regular language R is a regular separator of languages K and L if K ⊆ R and L ∩ R = ∅. It was shown by Czerwiński, Lasota, Meyer, Muskalla, Kumar, and Saivasan (CONCUR 2018) that it is decidable whether, for two given VASS, there exists a regular separator. In fact, they show that a regular separator exists if and only if the two VASS languages are disjoint. However, they provide a triply exponential upper bound and a doubly exponential lower bound for the size of such separators and leave open which bound is tight. We show that if two VASS have disjoint languages, then there exists a regular separator with at most doubly exponential size. Moreover, we provide tight size bounds for separators in the case of fixed dimensions and unary/binary encodings of updates and NFA/DFA separators. In particular, we settle the aforementioned question. The key ingredient in the upper bound is a structural analysis of separating automata based on the concept of basic separators, which was recently introduced by Czerwiński and the second author. This allows us to determinize (and thus complement) without the powerset construction and avoid one exponential blowup.
Cite as

Chris Köcher and Georg Zetzsche. Regular Separators for VASS Coverability Languages. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kocher_et_al:LIPIcs.FSTTCS.2023.15,
  author =	{K\"{o}cher, Chris and Zetzsche, Georg},
  title =	{{Regular Separators for VASS Coverability Languages}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.15},
  URN =		{urn:nbn:de:0030-drops-193883},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.15},
  annote =	{Keywords: Vector Addition System, Separability, Regular Language}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.84
An Empirical Evaluation of k-Means Coresets

Authors: Chris Schwiegelshohn and Omar Ali Sheikh-Omar

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Coresets are among the most popular paradigms for summarizing data. In particular, there exist many high performance coresets for clustering problems such as k-means in both theory and practice. Curiously, there exists no work on comparing the quality of available k-means coresets. In this paper we perform such an evaluation. There currently is no algorithm known to measure the distortion of a candidate coreset. We provide some evidence as to why this might be computationally difficult. To complement this, we propose a benchmark for which we argue that computing coresets is challenging and which also allows us an easy (heuristic) evaluation of coresets. Using this benchmark and real-world data sets, we conduct an exhaustive evaluation of the most commonly used coreset algorithms from theory and practice.
Cite as

Chris Schwiegelshohn and Omar Ali Sheikh-Omar. An Empirical Evaluation of k-Means Coresets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{schwiegelshohn_et_al:LIPIcs.ESA.2022.84,
  author =	{Schwiegelshohn, Chris and Sheikh-Omar, Omar Ali},
  title =	{{An Empirical Evaluation of k-Means Coresets}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{84:1--84:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.84},
  URN =		{urn:nbn:de:0030-drops-170225},
  doi =		{10.4230/LIPIcs.ESA.2022.84},
  annote =	{Keywords: coresets, k-means coresets, evaluation, benchmark}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.71
Approximate Degree, Secret Sharing, and Concentration Phenomena

Authors: Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The epsilon-approximate degree deg~_epsilon(f) of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are: - We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg~_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg~_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg~_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.
Cite as

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71,
  author =	{Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher},
  title =	{{Approximate Degree, Secret Sharing, and Concentration Phenomena}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{71:1--71:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.71},
  URN =		{urn:nbn:de:0030-drops-112869},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.71},
  annote =	{Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.71
Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Authors: Huan Li, He Sun, and Luca Zanetti

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.
Cite as

Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2019.71,
  author =	{Li, Huan and Sun, He and Zanetti, Luca},
  title =	{{Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.71},
  URN =		{urn:nbn:de:0030-drops-111926},
  doi =		{10.4230/LIPIcs.ESA.2019.71},
  annote =	{Keywords: Spectral methods, Hermitian Laplacians, the Max-2-Lin problem, Unique Games}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.9
The Cayley-Graph of the Queue Monoid: Logic and Decidability

Authors: Faried Abu Zaid and Chris Köcher

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We investigate the decidability of logical aspects of graphs that arise as Cayley-graphs of the so-called queue monoids. These monoids model the behavior of the classical (reliable) fifo-queues. We answer a question raised by Huschenbett, Kuske, and Zetzsche and prove the decidability of the first-order theory of these graphs with the help of an - at least for the authors - new combination of the well-known method from Ferrante and Rackoff and an automata-based approach. On the other hand, we prove that the monadic second-order of the queue monoid's Cayley-graph is undecidable.
Cite as

Faried Abu Zaid and Chris Köcher. The Cayley-Graph of the Queue Monoid: Logic and Decidability. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abuzaid_et_al:LIPIcs.FSTTCS.2018.9,
  author =	{Abu Zaid, Faried and K\"{o}cher, Chris},
  title =	{{The Cayley-Graph of the Queue Monoid: Logic and Decidability}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.9},
  URN =		{urn:nbn:de:0030-drops-99088},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.9},
  annote =	{Keywords: Queues, Transformation Monoid, Cayley-Graph, Logic, First-Order Theory, MSO Theory, Model Checking}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.45
Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid

Authors: Chris Köcher

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Partially lossy queue monoids (or plq monoids) model the behavior of queues that can forget arbitrary parts of their content. While many decision problems on recognizable subsets in the plq monoid are decidable, most of them are undecidable if the sets are rational. In particular, in this monoid the classes of rational and recognizable subsets do not coincide. By restricting multiplication and iteration in the construction of rational sets and by allowing complementation we obtain precisely the class of recognizable sets. From these special rational expressions we can obtain an MSO logic describing the recognizable subsets. Moreover, we provide similar results for the class of aperiodic subsets in the plq monoid.
Cite as

Chris Köcher. Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kocher:LIPIcs.STACS.2018.45,
  author =	{K\"{o}cher, Chris},
  title =	{{Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.45},
  URN =		{urn:nbn:de:0030-drops-84839},
  doi =		{10.4230/LIPIcs.STACS.2018.45},
  annote =	{Keywords: Partially Lossy Queues, Transformation Monoid, Rational Sets, Recognizable Sets, Aperiodic Sets, MSO logic}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.50
On Multidimensional and Monotone k-SUM

Authors: Chloe Ching-Yun Hsu and Chris Umans

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The well-known k-SUM conjecture is that integer k-SUM requires time Omega(n^{\ceil{k/2}-o(1)}). Recent work has studied multidimensional k-SUM in F_p^d, where the best known algorithm takes time \tilde O(n^{\ceil{k/2}}). Bhattacharyya et al. [ICS 2011] proved a min(2^{\Omega(d)},n^{\Omega(k)}) lower bound for k-SUM in F_p^d under the Exponential Time Hypothesis. We give a more refined lower bound under the standard k-SUM conjecture: for sufficiently large p, k-SUM in F_p^d requires time Omega(n^{k/2-o(1)}) if k is even, and Omega(n^{\ceil{k/2}-2k(log k)/(log p)-o(1)}) if k is odd. For a special case of the multidimensional problem, bounded monotone d-dimensional 3SUM, Chan and Lewenstein [STOC 2015] gave a surprising \tilde O(n^{2-2/(d+13)}) algorithm using additive combinatorics. We show this algorithm is essentially optimal. To be more precise, bounded monotone d-dimensional 3SUM requires time Omega(n^{2-\frac{4}{d}-o(1)}) under the standard 3SUM conjecture, and time Omega(n^{2-\frac{2}{d}-o(1)}) under the so-called strong 3SUM conjecture. Thus, even though one might hope to further exploit the structural advantage of monotonicity, no substantial improvements beyond those obtained by Chan and Lewenstein are possible for bounded monotone d-dimensional 3SUM.
Cite as

Chloe Ching-Yun Hsu and Chris Umans. On Multidimensional and Monotone k-SUM. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.MFCS.2017.50,
  author =	{Hsu, Chloe Ching-Yun and Umans, Chris},
  title =	{{On Multidimensional and Monotone k-SUM}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.50},
  URN =		{urn:nbn:de:0030-drops-80618},
  doi =		{10.4230/LIPIcs.MFCS.2017.50},
  annote =	{Keywords: 3SUM, kSUM, monotone 3SUM, strong 3SUM conjecture}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2017.1
Everest: Towards a Verified, Drop-in Replacement of HTTPS

Authors: Karthikeyan Bhargavan, Barry Bond, Antoine Delignat-Lavaud, Cédric Fournet, Chris Hawblitzel, Catalin Hritcu, Samin Ishtiaq, Markulf Kohlweiss, Rustan Leino, Jay Lorch, Kenji Maillard, Jianyang Pan, Bryan Parno, Jonathan Protzenko, Tahina Ramananandro, Ashay Rane, Aseem Rastogi, Nikhil Swamy, Laure Thompson, Peng Wang, Santiago Zanella-Béguelin, and Jean-Karim Zinzindohoué

Published in: LIPIcs, Volume 71, 2nd Summit on Advances in Programming Languages (SNAPL 2017)

Abstract
The HTTPS ecosystem is the foundation on which Internet security is built. At the heart of this ecosystem is the Transport Layer Security (TLS) protocol, which in turn uses the X.509 public-key infrastructure and numerous cryptographic constructions and algorithms. Unfortunately, this ecosystem is extremely brittle, with headline-grabbing attacks and emergency patches many times a year. We describe our ongoing efforts in Everest (The Everest VERified End-to-end Secure Transport) a project that aims to build and deploy a verified version of TLS and other components of HTTPS, replacing the current infrastructure with proven, secure software. Aiming both at full verification and usability, we conduct high-level code-based, game-playing proofs of security on cryptographic implementations that yield efficient, deployable code, at the level of C and assembly. Concretely, we use F*, a dependently typed language for programming, meta-programming, and proving at a high level, while relying on low-level DSLs embedded within F* for programming low-level components when necessary for performance and, sometimes, side-channel resistance. To compose the pieces, we compile all our code to source-like C and assembly, suitable for deployment and integration with existing code bases, as well as audit by independent security experts. Our main results so far include (1) the design of Low*, a subset of F* designed for C-like imperative programming but with high-level verification support, and KreMLin, a compiler that extracts Low* programs to C; (2) an implementation of the TLS-1.3 record layer in Low*, together with a proof of its concrete cryptographic security; (3) Vale, a new DSL for verified assembly language, and several optimized cryptographic primitives proven functionally correct and side-channel resistant. In an early deployment, all our verified software is integrated and deployed within libcurl, a widely used library of networking protocols.
Cite as

Karthikeyan Bhargavan, Barry Bond, Antoine Delignat-Lavaud, Cédric Fournet, Chris Hawblitzel, Catalin Hritcu, Samin Ishtiaq, Markulf Kohlweiss, Rustan Leino, Jay Lorch, Kenji Maillard, Jianyang Pan, Bryan Parno, Jonathan Protzenko, Tahina Ramananandro, Ashay Rane, Aseem Rastogi, Nikhil Swamy, Laure Thompson, Peng Wang, Santiago Zanella-Béguelin, and Jean-Karim Zinzindohoué. Everest: Towards a Verified, Drop-in Replacement of HTTPS. In 2nd Summit on Advances in Programming Languages (SNAPL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 71, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bhargavan_et_al:LIPIcs.SNAPL.2017.1,
  author =	{Bhargavan, Karthikeyan and Bond, Barry and Delignat-Lavaud, Antoine and Fournet, C\'{e}dric and Hawblitzel, Chris and Hritcu, Catalin and Ishtiaq, Samin and Kohlweiss, Markulf and Leino, Rustan and Lorch, Jay and Maillard, Kenji and Pan, Jianyang and Parno, Bryan and Protzenko, Jonathan and Ramananandro, Tahina and Rane, Ashay and Rastogi, Aseem and Swamy, Nikhil and Thompson, Laure and Wang, Peng and Zanella-B\'{e}guelin, Santiago and Zinzindohou\'{e}, Jean-Karim},
  title =	{{Everest: Towards a Verified, Drop-in Replacement of HTTPS}},
  booktitle =	{2nd Summit on Advances in Programming Languages (SNAPL 2017)},
  pages =	{1:1--1:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-032-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{71},
  editor =	{Lerner, Benjamin S. and Bod{\'\i}k, Rastislav and Krishnamurthi, Shriram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2017.1},
  URN =		{urn:nbn:de:0030-drops-71196},
  doi =		{10.4230/LIPIcs.SNAPL.2017.1},
  annote =	{Keywords: Security, Cryptography, Verification, TLS}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.3
Hardness of Approximation for H-Free Edge Modification Problems

Authors: Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free, that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H, with several important exceptions occurring when the class of H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free Edge Completion are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the Exponential Time Hypothesis fails. The assumption of the existence of two non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the \minhorn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.
Cite as

Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bliznets_et_al:LIPIcs.APPROX-RANDOM.2016.3,
  author =	{Bliznets, Ivan and Cygan, Marek and Komosa, Pawel and Pilipczuk, Michal},
  title =	{{Hardness of Approximation for H-Free Edge Modification Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.3},
  URN =		{urn:nbn:de:0030-drops-66260},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.3},
  annote =	{Keywords: hardness of approximation, parameterized complexity, kernelization, edge modification problems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.4
On Approximating Target Set Selection

Authors: Moses Charikar, Yonatan Naamad, and Anthony Wirth

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
We study the Target Set Selection (TSS) problem introduced by Kempe, Kleinberg, and Tardos (2003). This problem models the propagation of influence in a network, in a sequence of rounds. A set of nodes is made "active" initially. In each subsequent round, a vertex is activated if at least a certain number of its neighbors are (already) active. In the minimization version, the goal is to activate a small set of vertices initially - a seed, or target, set - so that activation spreads to the entire graph. In the absence of a sublinear-factor algorithm for the general version, we provide a (sublinear) approximation algorithm for the bounded-round version, where the goal is to activate all the vertices in r rounds. Assuming a known conjecture on the hardness of Planted Dense Subgraph, we establish hardness-of-approximation results for the bounded-round version. We show that they translate to general Target Set Selection, leading to a hardness factor of n^(1/2-epsilon) for all epsilon > 0. This is the first polynomial hardness result for Target Set Selection, and the strongest conditional result known for a large class of monotone satisfiability problems. In the maximization version of TSS, the goal is to pick a target set of size k so as to maximize the number of nodes eventually active. We show an n^(1-epsilon) hardness result for the undirected maximization version of the problem, thus establishing that the undirected case is as hard as the directed case. Finally, we demonstrate an SETH lower bound for the exact computation of the optimal seed set.
Cite as

Moses Charikar, Yonatan Naamad, and Anthony Wirth. On Approximating Target Set Selection. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{charikar_et_al:LIPIcs.APPROX-RANDOM.2016.4,
  author =	{Charikar, Moses and Naamad, Yonatan and Wirth, Anthony},
  title =	{{On Approximating Target Set Selection}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.4},
  URN =		{urn:nbn:de:0030-drops-66274},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.4},
  annote =	{Keywords: target set selection, influence propagation, approximation algorithms, hardness of approximation, planted dense subgraph}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.6
The Densest k-Subhypergraph Problem

Authors: Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
The Densest k-Subgraph (DkS) problem, and its corresponding minimization problem Smallest p-Edge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest k-Subhypergraph problem (given a hypergraph (V, E), find a subset W subseteq V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an O(n^{4(4-sqrt{3})/13 + epsilon}) <= O(n^{0.697831+epsilon})-approximation (for arbitrary constant epsilon > 0) for Densest k-Subhypergraph and an ~O(n^{2/5})-approximation for Minimum p-Union. We also give an O(sqrt{m})-approximation for Minimum p-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.
Cite as

Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. The Densest k-Subhypergraph Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2016.6,
  author =	{Chlamtac, Eden and Dinitz, Michael and Konrad, Christian and Kortsarz, Guy and Rabanca, George},
  title =	{{The Densest k-Subhypergraph Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  URN =		{urn:nbn:de:0030-drops-66298},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.6},
  annote =	{Keywords: Hypergraphs, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.9
A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

Authors: Nir Halman

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Given n elements with nonnegative integer weights w=(w_1,...,w_n), an integer capacity C and positive integer ranges u=(u_1,...,u_n), we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most C. We give a deterministic algorithm that estimates the number of solutions to within relative error epsilon in time polynomial in n, log U and 1/epsilon, where U=max_i u_i. More precisely, our algorithm runs in O((n^3 log^2 U)/epsilon) log (n log U)/epsilon) time. This is an improvement of n^2 and 1/epsilon (up to log terms) over the best known deterministic algorithm by Gopalan et al. [FOCS, (2011), pp. 817-826]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of binding constraints.
Cite as

Nir Halman. A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{halman:LIPIcs.APPROX-RANDOM.2016.9,
  author =	{Halman, Nir},
  title =	{{A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{9:1--9:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.9},
  URN =		{urn:nbn:de:0030-drops-66327},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.9},
  annote =	{Keywords: Approximate counting, integer knapsack, dynamic programming, bounding constraints, \$K\$-approximating sets and functions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.14
A Bi-Criteria Approximation Algorithm for k-Means

Authors: Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee alpha(beta) depending on the number beta*k of clusters that may be opened. Our guarantee alpha(beta) is always at most 9 + epsilon and improves rapidly with beta (for example: alpha(2) < 2.59, and alpha(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.
Cite as

Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward. A Bi-Criteria Approximation Algorithm for k-Means. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{makarychev_et_al:LIPIcs.APPROX-RANDOM.2016.14,
  author =	{Makarychev, Konstantin and Makarychev, Yury and Sviridenko, Maxim and Ward, Justin},
  title =	{{A Bi-Criteria Approximation Algorithm for k-Means}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.14},
  URN =		{urn:nbn:de:0030-drops-66370},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.14},
  annote =	{Keywords: k-means clustering, bicriteria approximation algorithms, linear programming, local search}
}
  • Refine by Author
  • 3 Köcher, Chris
  • 2 Coja-Oghlan, Amin
  • 2 Schwiegelshohn, Chris
  • 2 Slote, Joseph
  • 1 Abu Zaid, Faried
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Models of computation
  • 2 Theory of computation → Quantum computation theory
  • 1 Information systems → Clustering
  • 1 Information systems → Data structures
  • 1 Mathematics of computing → Mathematical analysis
  • Show More...

  • Refine by Keyword
  • 2 Belief Propagation
  • 2 Transformation Monoid
  • 2 approximate degree
  • 2 approximation algorithms
  • 2 hardness of approximation
  • Show More...

  • Refine by Type
  • 33 document

  • Refine by Publication Year
  • 22 2016
  • 2 2017
  • 2 2018
  • 2 2019
  • 2 2024
  • Show More...

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