21 Search Results for "Bhattacharyya, Arnab"

Document
DOI: 10.4230/LIPIcs.ESA.2024.12
Outlier Robust Multivariate Polynomial Regression

Authors: Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, and Esty Kelman

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We study the problem of robust multivariate polynomial regression: let p: ℝⁿ → ℝ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (𝐱_i,y_i) ∈ [-1,1]ⁿ × ℝ that are noisy versions of (𝐱_i,p(𝐱_i)). More precisely, each 𝐱_i is sampled independently from some distribution χ on [-1,1]ⁿ, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most ρ < 1/2, and otherwise satisfies |y_i-p(𝐱_i)| ≤ σ. The goal is to output a polynomial p̂, of degree at most d in each variable, within an 𝓁_∞-distance of at most O(σ) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n = 1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(dⁿlog d), where the hidden constant depends on n, if χ is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(σ), and the run-time depends on log(1/σ). In the setting where each 𝐱_i and y_i are known up to N bits of precision, the run-time’s dependence on N is linear. We also show that our sample complexities are optimal in terms of dⁿ. Furthermore, we show that it is possible to have the run-time be independent of 1/σ, at the cost of a higher sample complexity.
Cite as

Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, and Esty Kelman. Outlier Robust Multivariate Polynomial Regression. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arora_et_al:LIPIcs.ESA.2024.12,
  author =	{Arora, Vipul and Bhattacharyya, Arnab and Boban, Mathews and Guruswami, Venkatesan and Kelman, Esty},
  title =	{{Outlier Robust Multivariate Polynomial Regression}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.12},
  URN =		{urn:nbn:de:0030-drops-210830},
  doi =		{10.4230/LIPIcs.ESA.2024.12},
  annote =	{Keywords: Robust Statistics, Polynomial Regression, Sample Efficient Learning}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.30
Exact Minimum Weight Spanners via Column Generation

Authors: Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Given a weighted graph G, a minimum weight α-spanner is a least-weight subgraph H ⊆ G that preserves minimum distances between all node pairs up to a factor of α. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [Markus Chimani and Finn Stutzenstein, 2022]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [Sigurd and Zachariasen, 2004] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [Ahmed et al., 2019], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16 000 nodes within 13 min. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time.
Cite as

Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner. Exact Minimum Weight Spanners via Column Generation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.ESA.2024.30,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning and Wagner, Mirko H.},
  title =	{{Exact Minimum Weight Spanners via Column Generation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.30},
  URN =		{urn:nbn:de:0030-drops-211012},
  doi =		{10.4230/LIPIcs.ESA.2024.30},
  annote =	{Keywords: Graph spanners, ILP, algorithm engineering, experimental study}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.89
Locally Computing Edge Orientations

Authors: Slobodan Mitrović, Ronitt Rubinfeld, and Mihir Singhal

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider the question of orienting the edges in a graph G such that every vertex has bounded out-degree. For graphs of arboricity α, there is an orientation in which every vertex has out-degree at most α and, moreover, the best possible maximum out-degree of an orientation is at least α - 1. We are thus interested in algorithms that can achieve a maximum out-degree of close to α. A widely studied approach for this problem in the distributed algorithms setting is a "peeling algorithm" that provides an orientation with maximum out-degree α(2+ε) in a logarithmic number of iterations. We consider this problem in the local computation algorithm (LCA) model, which quickly answers queries of the form "What is the orientation of edge (u,v)?" by probing the input graph. When the peeling algorithm is executed in the LCA setting by applying standard techniques, e.g., the Parnas-Ron paradigm, it requires Ω(n) probes per query on an n-vertex graph. In the case where G has unbounded degree, we show that any LCA that orients its edges to yield maximum out-degree r must use Ω(√ n/r) probes to G per query in the worst case, even if G is known to be a forest (that is, α = 1). We also show several algorithms with sublinear probe complexity when G has unbounded degree. When G is a tree such that the maximum degree Δ of G is bounded, we demonstrate an algorithm that uses Δ n^{1-log_Δ r + o(1)} probes to G per query. To obtain this result, we develop an edge-coloring approach that ultimately yields a graph-shattering-like result. We also use this shattering-like approach to demonstrate an LCA which 4-colors any tree using sublinear probes per query.
Cite as

Slobodan Mitrović, Ronitt Rubinfeld, and Mihir Singhal. Locally Computing Edge Orientations. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mitrovic_et_al:LIPIcs.ESA.2024.89,
  author =	{Mitrovi\'{c}, Slobodan and Rubinfeld, Ronitt and Singhal, Mihir},
  title =	{{Locally Computing Edge Orientations}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{89:1--89:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.89},
  URN =		{urn:nbn:de:0030-drops-211603},
  doi =		{10.4230/LIPIcs.ESA.2024.89},
  annote =	{Keywords: local computation algorithms, edge orientation, tree coloring}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.37
Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions

Authors: Hadley Black

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

Abstract
We study monotonicity testing of functions f : {0,1}^d → {0,1} using sample-based algorithms, which are only allowed to observe the value of f on points drawn independently from the uniform distribution. A classic result by Bshouty-Tamon (J. ACM 1996) proved that monotone functions can be learned with exp(Õ(min{(1/ε)√d,d})) samples and it is not hard to show that this bound extends to testing. Prior to our work the only lower bound for this problem was Ω(√{exp(d)/ε}) in the small ε parameter regime, when ε = O(d^{-3/2}), due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of monotonicity testing was wide open for ε ≫ d^{-3/2}. We resolve this question, obtaining a nearly tight lower bound of exp(Ω(min{(1/ε)√d,d})) for all ε at most a sufficiently small constant. In fact, we prove a much more general result, showing that the sample complexity of k-monotonicity testing and learning for functions f : {0,1}^d → [r] is exp(Ω(min{(rk/ε)√d,d})). For testing with one-sided error we show that the sample complexity is exp(Ω(d)). Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of d,k,r,1/ε in the exponent) of exp(Θ̃(min{(rk/ε)√d,d})) on the sample complexity of testing and learning measurable k-monotone functions f : ℝ^d → [r] under product distributions. Our upper bound improves upon the previous bound of exp(Õ(min{(k/ε²)√d,d})) by Harms-Yoshida (ICALP 2022) for Boolean functions (r = 2).
Cite as

Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37,
  author =	{Black, Hadley},
  title =	{{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  URN =		{urn:nbn:de:0030-drops-210308},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  annote =	{Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.38
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Authors: Nader H. Bshouty and George Haddad

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

Abstract
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:ℝ^+ → ℝ^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ^{-1}(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n) ≤ n relevant variables), where k(n) = ω_n(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Γ(n))T(Γ(n)²)-time algorithm that properly learns parities, where Γ(x) = γ(γ(x)). If T(Γ(n)²) = exp({o(n/log n)}), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).
Cite as

Nader H. Bshouty and George Haddad. Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.APPROX/RANDOM.2024.38,
  author =	{Bshouty, Nader H. and Haddad, George},
  title =	{{Approximating the Number of Relevant Variables in a Parity Implies Proper Learning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  URN =		{urn:nbn:de:0030-drops-210316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  annote =	{Keywords: PAC Learning, Random Classification Noise, Uniform Distribution, Parity, Sparcity Approximation}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.48
Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries

Authors: Tomer Adar, Eldar Fischer, and Amit Levi

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

Abstract
We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for n-dimensional distributions that is quasi-linear in n, improving the previously known Õ(n²/ε²) query complexity bound to Õ(n/ε²). We extend this result to general finite alphabets with logarithmic cost in the alphabet size. By exploiting the specific structure of the queries that we use (which are more restrictive than general subcube queries), we obtain a cubic improvement over the best known test for distributions over {1,…,N} under the interval querying model of Canonne, Ron and Servedio (2015), attaining a query complexity of Õ((log N)/ε²), which for fixed ε almost matches the known lower bound of Ω((log N)/log log N). We also derive a product test for n-dimensional distributions with Õ(n/ε²) queries, and provide an Ω(√n/ε²) lower bound for this property.
Cite as

Tomer Adar, Eldar Fischer, and Amit Levi. Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 48:1-48:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2024.48,
  author =	{Adar, Tomer and Fischer, Eldar and Levi, Amit},
  title =	{{Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{48:1--48:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.48},
  URN =		{urn:nbn:de:0030-drops-210418},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.48},
  annote =	{Keywords: Distribution testing, conditional sampling, sub-cube sampling}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.8
Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed n-bit RLCCs with O(log^{69} n) queries. Their construction relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs. As for lower bounds, Gur and Lachish (SICOMP 2021) proved that any asymptotically-good RLCC must make Ω̃(√{log n}) queries. Hence emerges the intriguing question regarding the identity of the least value 1/2 ≤ e ≤ 69 for which asymptotically-good RLCCs with query complexity (log n)^{e+o(1)} exist. In this work, we make substantial progress in narrowing the gap by devising asymptotically-good RLCCs with a query complexity of (log n)^{2+o(1)}. The key insight driving our work lies in recognizing that the strong guarantee of local testability overshoots the requirements for the Kumar-Mon reduction. In particular, we prove that we can replace the LTCs by "vanilla" expander codes which indeed have the necessary property: local testability in the code’s vicinity.
Cite as

Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.8},
  URN =		{urn:nbn:de:0030-drops-204045},
  doi =		{10.4230/LIPIcs.CCC.2024.8},
  annote =	{Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.10
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

Authors: Xin Li and Yan Zhong

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
Affine extractors give some of the best-known lower bounds for various computational models, such as AC⁰ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudlák, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalization of ROBPs where each node can make linear queries, and showed that the former implies strong lower bound for a certain type of the latter known as strongly read-once linear branching programs (SROLBPs). Their main result gives explicit constructions of directional affine extractors for entropy k > 2n/3, which implies average-case complexity 2^{n/3-o(n)} against SROLBPs with exponentially small correlation. A follow-up work by Chattopadhyay and Liao (CCC' 23) improves the hardness to 2^{n-o(n)} at the price of increasing the correlation to polynomially large, via a new connection to sumset extractors introduced by Chattopadhyay and Li (STOC' 16) and explicit constructions of such extractors by Chattopadhyay and Liao (STOC' 22). Both works left open the questions of better constructions of directional affine extractors and improved average-case complexity against SROLBPs in the regime of small correlation. This paper provides a much more in-depth study of directional affine extractors, SROLBPs, and ROBPs. Our main results include: - An explicit construction of directional affine extractors with k = o(n) and exponentially small error, which gives average-case complexity 2^{n-o(n)} against SROLBPs with exponentially small correlation, thus answering the two open questions raised in previous works. - An explicit function in AC⁰ that gives average-case complexity 2^{(1-δ)n} against ROBPs with negligible correlation, for any constant δ > 0. Previously, no such average-case hardness is known, and the best size lower bound for any function in AC⁰ against ROBPs is 2^Ω(n). One of the key ingredients in our constructions is a new linear somewhere condenser for affine sources, which is based on dimension expanders. The condenser also leads to an unconditional improvement of the entropy requirement of explicit affine extractors with negligible error. We further show that the condenser also works for general weak random sources, under the Polynomial Freiman-Ruzsa Theorem in 𝖥₂ⁿ, recently proved by Gowers, Green, Manners, and Tao (arXiv' 23).
Cite as

Xin Li and Yan Zhong. Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.CCC.2024.10,
  author =	{Li, Xin and Zhong, Yan},
  title =	{{Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.10},
  URN =		{urn:nbn:de:0030-drops-204060},
  doi =		{10.4230/LIPIcs.CCC.2024.10},
  annote =	{Keywords: Randomness Extractors, Affine, Read-once Linear Branching Programs, Low-degree polynomials, AC⁰ circuits}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.24
Distribution-Free Proofs of Proximity

Authors: Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions f: [n] → {0,1} having a certain property Π and reject functions that are ε-far from Π, where the distance is measured according to an arbitrary and unknown input distribution 𝒟 ∼ [n]. As usual in property testing, the tester is required to do so while making only a sublinear number of input queries, but as the distribution is unknown, we also allow a sublinear number of samples from the distribution 𝒟. In this work we initiate the study of distribution-free interactive proofs of proximity (df-IPPs) in which the distribution-free testing algorithm is assisted by an all powerful but untrusted prover. Our main result is that for any problem Π ∈ NC, any proximity parameter ε > 0, and any (trade-off) parameter τ ≤ √n, we construct a df-IPP for Π with respect to ε, that has query and sample complexities τ+O(1/ε), and communication complexity Õ(n/τ + 1/ε). For τ as above and sufficiently large ε (namely, when ε > τ/n), this result matches the parameters of the best-known general purpose IPPs in the standard uniform setting. Moreover, for such τ, its parameters are optimal up to poly-logarithmic factors under reasonable cryptographic assumptions for the same regime of ε as the uniform setting, i.e., when ε ≥ 1/τ. For smaller values of ε (i.e., when ε < τ/n), our protocol has communication complexity Ω(1/ε), which is worse than the Õ(n/τ) communication complexity of the uniform IPPs (with the same query complexity). With the aim of improving on this gap, we further show that for IPPs over specialised, but large distribution families, such as sufficiently smooth distributions and product distributions, the communication complexity can be reduced to Õ(n/τ^{1-o(1)}). In addition, we show that for certain natural families of languages, such as symmetric and (relaxed) self-correctable languages, it is possible to further improve the efficiency of distribution-free IPPs.
Cite as

Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum. Distribution-Free Proofs of Proximity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2024.24,
  author =	{Aaronson, Hugo and Gur, Tom and Rajgopal, Ninad and Rothblum, Ron D.},
  title =	{{Distribution-Free Proofs of Proximity}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.24},
  URN =		{urn:nbn:de:0030-drops-204204},
  doi =		{10.4230/LIPIcs.CCC.2024.24},
  annote =	{Keywords: Property Testing, Interactive Proofs, Distribution-Free Property Testing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.67
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification

Authors: Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the Directed Steiner Network problem, the input is a directed graph G, a set T ⊆ V(G) of k terminals, and a demand graph D on T. The task is to find a subgraph H ⊆ G with the minimum number of edges such that for every (s,t) ∈ E(D), the solution H contains a directed s → t path. The goal of this paper is to investigate how the complexity of the problem depends on the demand pattern in planar graphs. Formally, if 𝒟 is a class of directed graphs, then the 𝒟-Steiner Network (𝒟-DSN) problem is the special case where the demand graph D is restricted to be from 𝒟. We give a complete characterization of the behavior of every 𝒟-DSN problem on planar graphs. We classify every class 𝒟 closed under transitive equivalence and identification of vertices into three cases: assuming ETH, either the problem is 1) solvable in time 2^O(k)⋅n^O(1), i.e., FPT parameterized by the number k of terminals, but not solvable in time 2^o(k)⋅n^O(1), 2) solvable in time f(k)⋅n^O(√k), but cannot be solved in time f(k)⋅n^o(√k), or 3) solvable in time f(k)⋅n^O(k), but cannot be solved in time f(k)⋅n^o(k). Our result is a far-reaching generalization and unification of earlier results on Directed Steiner Tree, Directed Steiner Network, and Strongly Connected Steiner Subgraph on planar graphs. As an important step of our lower bound proof, we discover a rare example of a genuinely planar problem (i.e., described by a planar graph and two sets of vertices) that cannot be solved in time f(k)⋅n^o(k): given two sets of terminals S and T with |S|+|T| = k, find a subgraph with minimum number of edges such that every vertex of T is reachable from every vertex of S.
Cite as

Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67,
  author =	{Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani},
  title =	{{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.67},
  URN =		{urn:nbn:de:0030-drops-202104},
  doi =		{10.4230/LIPIcs.ICALP.2024.67},
  annote =	{Keywords: Directed Steiner Network, Sub-exponential algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.107
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH

Authors: Shuangle Li, Bingkai Lin, and Yuwei Liu

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we present a new gap-creating randomized self-reduction for the parameterized Maximum Likelihood Decoding problem over 𝔽_p (k-MLD_p). The reduction takes a k-MLD_p instance with k⋅ n d-dimensional vectors as input, runs in O(d2^{O(k)}n^{1.01}) time for some computable function f, outputs a (3/2-ε)-Gap-k'-MLD_p instance for any ε > 0, where k' = O(k²log k). Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate k-MLD_p (and therefore its dual problem k-NCP_p) within factor (3/2-ε) in f(k)⋅ n^{o(√{k/log k})} time for any ε > 0. We then use reduction by Bhattacharyya, Ghoshal, Karthik and Manurangsi (ICALP 2018) to amplify the (3/2-ε)-gap to any constant. As a result, we show that assuming ETH, no algorithms can approximate k-NCP_p and k-MDP_p within γ-factor in f(k)⋅ n^{o(k^{ε_γ})} time for some constant ε_γ > 0. Combining with the gap-preserving reduction by Bennett, Cheraghchi, Guruswami and Ribeiro (STOC 2023), we also obtain similar lower bounds for k-MDP_p, k-CVP_p and k-SVP_p. These results improve upon the previous f(k)⋅ n^{Ω(poly log k)} lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J.ACM 2021) and Bennett et al. (STOC 2023).
Cite as

Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2024.107,
  author =	{Li, Shuangle and Lin, Bingkai and Liu, Yuwei},
  title =	{{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{107:1--107:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107},
  URN =		{urn:nbn:de:0030-drops-202500},
  doi =		{10.4230/LIPIcs.ICALP.2024.107},
  annote =	{Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.112
Testing Spreading Behavior in Networks with Arbitrary Topologies

Authors: Augusto Modanese and Yuichi Yoshida

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Given the full topology of a network, how hard is it to test if it is evolving according to a local rule or is far from doing so? Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every "infected" node stays infected forever, and each "healthy" node becomes infected if and only if it has at least one infected neighbor. Our results are subdivided into two main groups: - If we are testing a single time step of evolution, then the query complexity is O(Δ/ε) or Õ(√n/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and the number of vertices in the underlying graph, respectively. We also give lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ = o(√n) and Δ = O(n^{1/3}), respectively. If ε is constant, then the first of these also holds against adaptive testers. - When testing the environment over T time steps, we have two algorithms that need O(Δ^{T-1}/εT) and Õ(|E|/εT) queries, respectively, where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T = 2.
Cite as

Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 112:1-112:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{modanese_et_al:LIPIcs.ICALP.2024.112,
  author =	{Modanese, Augusto and Yoshida, Yuichi},
  title =	{{Testing Spreading Behavior in Networks with Arbitrary Topologies}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{112:1--112:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.112},
  URN =		{urn:nbn:de:0030-drops-202554},
  doi =		{10.4230/LIPIcs.ICALP.2024.112},
  annote =	{Keywords: Property testing, bootstrap percolation, local phenomena, expander graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.11
Property Testing with Online Adversaries

Authors: Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova

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

Abstract
The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt t data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include t < 1, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.
Cite as

Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property Testing with Online Adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2024.11,
  author =	{Ben-Eliezer, Omri and Kelman, Esty and Meir, Uri and Raskhodnikova, Sofya},
  title =	{{Property Testing with Online Adversaries}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{11:1--11:25},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.11},
  URN =		{urn:nbn:de:0030-drops-195395},
  doi =		{10.4230/LIPIcs.ITCS.2024.11},
  annote =	{Keywords: Linearity testing, low-degree testing, Reed-Muller codes, testing properties of sequences, erasure-resilience, corruption-resilience}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.37
Learning and Testing Variable Partitions

Authors: Andrej Bogdanov and Baoxiang Wang

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Let F be a multivariate function from a product set Σ^n to an Abelian group G. A k-partition of F with cost δ is a partition of the set of variables V into k non-empty subsets (X_1, ̇s, X_k) such that F(V) is δ-close to F_1(X_1)+ ̇s+F_k(X_k) for some F_1, ̇s, F_k with respect to a given error metric. We study algorithms for agnostically learning k partitions and testing k-partitionability over various groups and error metrics given query access to F. In particular we show that 1) Given a function that has a k-partition of cost δ, a partition of cost O(k n^2)(δ + ε) can be learned in time Õ(n^2 poly 1/ε) for any ε > 0. In contrast, for k = 2 and n = 3 learning a partition of cost δ + ε is NP-hard. 2) When F is real-valued and the error metric is the 2-norm, a 2-partition of cost √(δ^2 + ε) can be learned in time Õ(n^5/ε^2). 3) When F is Z_q-valued and the error metric is Hamming weight, k-partitionability is testable with one-sided error and O(kn^3/ε) non-adaptive queries. We also show that even two-sided testers require Ω(n) queries when k = 2. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.
Cite as

Andrej Bogdanov and Baoxiang Wang. Learning and Testing Variable Partitions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2020.37,
  author =	{Bogdanov, Andrej and Wang, Baoxiang},
  title =	{{Learning and Testing Variable Partitions}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.37},
  URN =		{urn:nbn:de:0030-drops-117221},
  doi =		{10.4230/LIPIcs.ITCS.2020.37},
  annote =	{Keywords: partitioning, agnostic learning, property testing, sublinear-time algorithms, hypergraph cut, reinforcement learning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.85
Combinatorial Lower Bounds for 3-Query LDCs

Authors: Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
A code is called a q-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index i and a received word w close to an encoding of a message x, outputs x_i by querying only at most q coordinates of w. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for 3-query binary LDC’s of dimension k and length n, the best known bounds are: 2^{k^o(1)} ≥ n ≥ Ω ̃(k²). In this work, we take a second look at binary 3-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of Ω ̃(k²) for the length of strong 3-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to 2-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.
Cite as

Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.ITCS.2020.85,
  author =	{Bhattacharyya, Arnab and Chandran, L. Sunil and Ghoshal, Suprovat},
  title =	{{Combinatorial Lower Bounds for 3-Query LDCs}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{85:1--85:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.85},
  URN =		{urn:nbn:de:0030-drops-117704},
  doi =		{10.4230/LIPIcs.ITCS.2020.85},
  annote =	{Keywords: Coding theory, Graph theory, Hypergraphs}
}
  • Refine by Author
  • 8 Bhattacharyya, Arnab
  • 3 Ghoshal, Suprovat
  • 2 Gopi, Sivakanth
  • 2 Kelman, Esty
  • 1 Aaronson, Hugo
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 3 Theory of computation → Error-correcting codes
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Computing methodologies → Reinforcement learning
  • 1 Mathematics of computing → Probabilistic algorithms
  • Show More...

  • Refine by Keyword
  • 2 Locally correctable code
  • 2 Minimum Distance Problem
  • 2 Parameterized Complexity
  • 2 Property testing
  • 2 Shortest Vector Problem
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 13 2024
  • 3 2016
  • 2 2020
  • 1 2009
  • 1 2017
  • 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