20 Search Results for "Kothari, Pravesh K."

Document
DOI: 10.4230/LIPIcs.CCC.2024.3
Solving Unique Games over Globally Hypercontractive Graphs

Authors: Mitali Bafna and Dor Minzer

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

Abstract
We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct characterization of all small sets that violate the small-set expansion property. This class of graphs includes the Johnson and Grassmann graphs, which have played a pivotal role in recent PCP constructions for UG, and their generalizations via high-dimensional expanders. We show new rounding techniques for higher degree sum-of-squares (SoS) relaxations for worst-case optimization. In particular, our algorithm shows how to round "low-entropy" pseudodistributions, broadly extending the algorithmic framework of [Mitali Bafna et al., 2021]. At a high level, [Mitali Bafna et al., 2021] showed how to round pseudodistributions for problems where there is a "unique" good solution. We extend their framework by exhibiting a rounding for problems where there might be "few good solutions". Our result suggests that UG is easy on globally hypercontractive graphs, and therefore highlights the importance of graphs that lack such a characterization in the context of PCP reductions for UG.
Cite as

Mitali Bafna and Dor Minzer. Solving Unique Games over Globally Hypercontractive Graphs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bafna_et_al:LIPIcs.CCC.2024.3,
  author =	{Bafna, Mitali and Minzer, Dor},
  title =	{{Solving Unique Games over Globally Hypercontractive Graphs}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{3:1--3:15},
  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.3},
  URN =		{urn:nbn:de:0030-drops-203996},
  doi =		{10.4230/LIPIcs.CCC.2024.3},
  annote =	{Keywords: unique games, approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.46
On the Streaming Complexity of Expander Decomposition

Authors: Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali

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

Abstract
In this paper we study the problem of finding (ε, ϕ)-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a ϕ-expander, while the number of inter-cluster edges is only an ε fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a (O(ϕ log n), ϕ)-expander decomposition of an n-vertex graph using Õ(n/ϕ²) bits of space [Filtser, Kapralov, Makarov, ITCS'23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter ϕ is inherent. We move towards answering this question on two fronts. We prove that a (O(ϕ log n), ϕ)-expander decomposition can be found using Õ(n) space, for every ϕ. At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA'21]. The key advantage is that a classical sparsifier [Fung et al., STOC'11], with size independent of ϕ, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error. Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS'22], among others). We prove that any streaming algorithm that computes a sequence of (O(ϕ log n), ϕ)-expander decompositions requires Ω̃(n/ϕ) bits of space, even in insertion only streams.
Cite as

Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46,
  author =	{Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide},
  title =	{{On the Streaming Complexity of Expander Decomposition}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{46:1--46: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.46},
  URN =		{urn:nbn:de:0030-drops-201890},
  doi =		{10.4230/LIPIcs.ICALP.2024.46},
  annote =	{Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.74
Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

Authors: Guy Goldberg

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

Abstract
Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword. For uncorrupted codewords, and for every bit, the decoder must decode the bit correctly with high probability. However, for a noisy codeword, a relaxed local decoder is allowed to output a "rejection" symbol, indicating that the decoding failed. We study the power of adaptivity and two-sided error for RLDCs. Our main result is that if the underlying code is linear, adaptivity and two-sided error do not give any power to relaxed local decoding. We construct a reduction from adaptive, two-sided error relaxed local decoders to non-adaptive, one-sided error ones. That is, the reduction produces a relaxed local decoder that never errs or rejects if its input is a valid codeword and makes queries based on its internal randomness (and the requested index to decode), independently of the input. The reduction essentially maintains the query complexity, requiring at most one additional query. For any input, the decoder’s error probability increases at most two-fold. Furthermore, assuming the underlying code is in systematic form, where the original message is embedded as the first bits of its encoding, the reduction also conserves both the code itself and its rate and distance properties We base the reduction on our new notion of additive promise problems. A promise problem is additive if the sum of any two YES-instances is a YES-instance and the sum of any NO-instance and a YES-instance is a NO-instance. This novel framework captures both linear RLDCs and property testing (of linear properties), despite their significant differences. We prove that in general, algorithms for any additive promise problem do not gain power from adaptivity or two-sided error, and obtain the result for RLDCs as a special case. The result also holds for relaxed locally correctable codes (RLCCs), where a codeword bit should be recovered. As an application, we improve the best known lower bound for linear adaptive RLDCs. Specifically, we prove that such codes require block length of n ≥ k^{1+Ω(1/q²)}, where k denotes the message length and q denotes the number of queries.
Cite as

Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 74:1-74:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goldberg:LIPIcs.ICALP.2024.74,
  author =	{Goldberg, Guy},
  title =	{{Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{74:1--74: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.74},
  URN =		{urn:nbn:de:0030-drops-202174},
  doi =		{10.4230/LIPIcs.ICALP.2024.74},
  annote =	{Keywords: Locally decodable codes, Relaxed locally correctable codes, Relaxed locally decodable codes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.97
Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Authors: Yotam Kenneth and Robert Krauthgamer

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

Abstract
In cut sparsification, all cuts of a hypergraph H = (V,E,w) are approximated within 1±ε factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge e is provided by a splitting function g_e: 2^e → ℝ_+. This generalization is called a submodular hypergraph when the functions {g_e}_{e ∈ E} are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work studied the setting where H' is a reweighted sub-hypergraph of H, and measured the size of H' by the number of hyperedges in it. In this setting, we present two results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n = |V| and ε^{-1}; (ii) we propose a new parameter, called spread, and use it to obtain smaller sparsifiers in some cases. We also show that for a natural family of splitting functions, relaxing the requirement that H' be a reweighted sub-hypergraph of H yields a substantially smaller encoding of the cuts of H (almost a factor n in the number of bits). This is in contrast to graphs, where the most succinct representation is attained by reweighted subgraphs. A new tool in our construction of succinct representation is the notion of deformation, where a splitting function g_e is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions.
Cite as

Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kenneth_et_al:LIPIcs.ICALP.2024.97,
  author =	{Kenneth, Yotam and Krauthgamer, Robert},
  title =	{{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{97:1--97:17},
  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.97},
  URN =		{urn:nbn:de:0030-drops-202406},
  doi =		{10.4230/LIPIcs.ICALP.2024.97},
  annote =	{Keywords: Cut Sparsification, Submodular Hypergraphs, Succinct Representation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.111
Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree

Authors: Yury Makarychev, Max Ovsiankin, and Erasmo Tani

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

Abstract
We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a vector cost c_e ∈ ℝ_{≥0}^𝓁. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the 𝓁_p-norm of the obtained cost vector (we assume that p ≥ 1 is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results.
Cite as

Yury Makarychev, Max Ovsiankin, and Erasmo Tani. Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 111:1-111:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{makarychev_et_al:LIPIcs.ICALP.2024.111,
  author =	{Makarychev, Yury and Ovsiankin, Max and Tani, Erasmo},
  title =	{{Approximation Algorithms for 𝓁\underlinep-Shortest Path and 𝓁\underlinep-Group Steiner Tree}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{111:1--111: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.111},
  URN =		{urn:nbn:de:0030-drops-202542},
  doi =		{10.4230/LIPIcs.ICALP.2024.111},
  annote =	{Keywords: Shortest Path, Asymmetric Group Steiner Tree, Sum-of-Squares}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.117
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle

Authors: Aaron Potechin and Aaron Zhang

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

Abstract
We show that the minimum total coefficient size of a Nullstellensatz proof of the pigeonhole principle on n+1 pigeons and n holes is 2^{Θ(n)}. We also investigate the ordering principle and construct an explicit Nullstellensatz proof for the ordering principle on n elements with total coefficient size 2ⁿ - n.
Cite as

Aaron Potechin and Aaron Zhang. Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 117:1-117:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{potechin_et_al:LIPIcs.ICALP.2024.117,
  author =	{Potechin, Aaron and Zhang, Aaron},
  title =	{{Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{117:1--117: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.117},
  URN =		{urn:nbn:de:0030-drops-202604},
  doi =		{10.4230/LIPIcs.ICALP.2024.117},
  annote =	{Keywords: Proof complexity, Nullstellensatz, pigeonhole principle, coefficient size}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.15
Oblivious Algorithms for the Max-kAND Problem

Authors: Noah G. Singer

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

Abstract
Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-kAND problem. This is a class of simple, combinatorial algorithms which round each variable with probability depending only on a quantity called the variable’s bias. Our definition generalizes a class of algorithms defined by Feige and Jozeph (Algorithmica '15) for Max-DICUT, a special case of Max-2AND. For each oblivious algorithm, we design a so-called factor-revealing linear program (LP) which captures its worst-case instance, generalizing one of Feige and Jozeph for Max-DICUT. Then, departing from their work, we perform a fully explicit analysis of these (infinitely many!) LPs. In particular, we show that for all k, oblivious algorithms for Max-kAND provably outperform a special subclass of algorithms we call "superoblivious" algorithms. Our result has implications for streaming algorithms: Generalizing the result for Max-DICUT of Saxena, Singer, Sudan, and Velusamy (SODA'23), we prove that certain separation results hold between streaming models for infinitely many CSPs: for every k, O(log n)-space sketching algorithms for Max-kAND known to be optimal in o(√n)-space can be beaten in (a) O(log n)-space under a random-ordering assumption, and (b) O(n^{1-1/k} D^{1/k}) space under a maximum-degree-D assumption. Even in the previously-known case of Max-DICUT, our analytic proof gives a fuller, computer-free picture of these separation results.
Cite as

Noah G. Singer. Oblivious Algorithms for the Max-kAND Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{singer:LIPIcs.APPROX/RANDOM.2023.15,
  author =	{Singer, Noah G.},
  title =	{{Oblivious Algorithms for the Max-kAND Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.15},
  URN =		{urn:nbn:de:0030-drops-188409},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.15},
  annote =	{Keywords: streaming algorithm, approximation algorithm, constraint satisfaction problem (CSP), factor-revealing linear program}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.27
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

Authors: Tommaso d'Orsi and Luca Trevisan

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We define a novel notion of "non-backtracking" matrix associated to any symmetric matrix, and we prove a "Ihara-Bass" type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with k variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a p fraction of assignments, if the instance contains n variables and n^{k/2} / ε² constraints, we can efficiently compute a certificate that the optimum satisfies at most a p+O_k(ε) fraction of constraints. Previously, this was known for even k, but for odd k one needed n^{k/2} (log n)^{O(1)} / ε² random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck’s inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is o(n^⌈k/2⌉) and the third one cannot work when the number of constraints is o(n^{k/2} √{log n}). We further apply our techniques to obtain a new PTAS finding assignments for k-CSP instances with n^{k/2} / ε² constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.
Cite as

Tommaso d'Orsi and Luca Trevisan. A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dorsi_et_al:LIPIcs.CCC.2023.27,
  author =	{d'Orsi, Tommaso and Trevisan, Luca},
  title =	{{A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.27},
  URN =		{urn:nbn:de:0030-drops-182979},
  doi =		{10.4230/LIPIcs.CCC.2023.27},
  annote =	{Keywords: CSP, k-XOR, strong refutation, sum-of-squares, tensor, graph, hypergraph, non-backtracking walk}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.77
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm

Authors: Jun-Ting Hsieh and Pravesh K. Kothari

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this note, we describe a α_GW + Ω̃(1/d²)-factor approximation algorithm for Max-Cut on weighted graphs of degree ⩽ d. Here, α_GW ≈ 0.878 is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski, and Langberg [Feige et al., 2002] and Florén [Florén, 2016]. Our guarantee is obtained by a tighter analysis of the solution obtained by applying a natural local improvement procedure to the Goemans-Williamson rounding of the basic SDP strengthened with triangle inequalities.
Cite as

Jun-Ting Hsieh and Pravesh K. Kothari. Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 77:1-77:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hsieh_et_al:LIPIcs.ICALP.2023.77,
  author =	{Hsieh, Jun-Ting and Kothari, Pravesh K.},
  title =	{{Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{77:1--77:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.77},
  URN =		{urn:nbn:de:0030-drops-181291},
  doi =		{10.4230/LIPIcs.ICALP.2023.77},
  annote =	{Keywords: Max-Cut, approximation algorithm, semidefinite programming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.78
Ellipsoid Fitting up to a Constant

Authors: Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In [Saunderson, 2011; Saunderson et al., 2013], Saunderson, Parrilo, and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in ℝ^d that passes through v_1, v_2, …, v_m with high probability when the v_is are chosen independently from the standard Gaussian distribution N(0,I_d)? The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix X such that v_i^⊤ X v_i = 1 for every 1 ⩽ i ⩽ m - a natural example of a random semidefinite program. SPW conjectured that m = (1-o(1)) d²/4 with high probability. Very recently, Potechin, Turner, Venkat and Wein [Potechin et al., 2022] and Kane and Diakonikolas [Kane and Diakonikolas, 2022] proved that m ≳ d²/log^O(1) d via a certain natural, explicit construction. In this work, we give a substantially tighter analysis of their construction to prove that m ≳ d²/C for an absolute constant C > 0. This resolves one direction of the SPW conjecture up to a constant. Our analysis proceeds via the method of Graphical Matrix Decomposition that has recently been used to analyze correlated random matrices arising in various areas [Barak et al., 2019; Bafna et al., 2022]. Our key new technical tool is a refined method to prove singular value upper bounds on certain correlated random matrices that are tight up to absolute dimension-independent constants. In contrast, all previous methods that analyze such matrices lose logarithmic factors in the dimension.
Cite as

Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Ellipsoid Fitting up to a Constant. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hsieh_et_al:LIPIcs.ICALP.2023.78,
  author =	{Hsieh, Jun-Ting and Kothari, Pravesh K. and Potechin, Aaron and Xu, Jeff},
  title =	{{Ellipsoid Fitting up to a Constant}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.78},
  URN =		{urn:nbn:de:0030-drops-181304},
  doi =		{10.4230/LIPIcs.ICALP.2023.78},
  annote =	{Keywords: Semidefinite programming, random matrices, average-case complexity}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.42
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Authors: Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar

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

Abstract
Let H(k,n,p) be the distribution on k-uniform hypergraphs where every subset of [n] of size k is included as an hyperedge with probability p independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, ω(H), in hypergraphs H ∼ H(k,n,p). For example, for any constant p, with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of Õ(√n) on the clique number in polynomial time. This matches, up to polylog(n) factors, the best known certificate for the clique number in random graphs, which is the special case of k = 2. Prior to our work, the best known refutation algorithms [Amin Coja-Oghlan et al., 2004; Sarah R. Allen et al., 2015] rely on a reduction to the problem of refuting random k-XOR via Feige’s XOR trick [Uriel Feige, 2002], and yield a polynomially worse bound of Õ(n^{3/4}) on the clique number when p = O(1). Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovász theta semidefinite programming relaxation for cliques in hypergraphs.
Cite as

Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 42:1-42:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2022.42,
  author =	{Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter},
  title =	{{Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{42:1--42:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.42},
  URN =		{urn:nbn:de:0030-drops-171642},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.42},
  annote =	{Keywords: Planted clique, Average-case complexity, Spectral refutation, Random matrix theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.14
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs

Authors: Boaz Barak and Kunal Marwaha

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of randomized classical algorithms. 1) We prove that every (quantum or classical) one-local algorithm (where the value of a vertex only depends on its and its neighbors' state) achieves on D-regular graphs of girth > 5 a maximum cut of at most 1/2 + C/√D for C = 1/√2 ≈ 0.7071. This is the first such result showing that one-local algorithms achieve a value that is bounded away from the true optimum for random graphs, which is 1/2 + P_*/√D + o(1/√D) for P_* ≈ 0.7632 [Dembo et al., 2017]. 2) We show that there is a classical k-local algorithm that achieves a value of 1/2 + C/√D - O(1/√k) for D-regular graphs of girth > 2k+1, where C = 2/π ≈ 0.6366. This is an algorithmic version of the existential bound of [Lyons, 2017] and is related to the algorithm of [Aizenman et al., 1987] (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs [M. B. Hastings, 2019; Marwaha, 2021]. 3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random D-regular graphs, as well as other natural instances, including graphs that do have short cycles. While our theoretical bounds require the locality and girth assumptions, our experimental work suggests that it could be possible to extend them beyond these constraints. This points at the tantalizing possibility that O(1)-local quantum maximum-cut algorithms might be pointwise dominated by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality on every possible instance. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.
Cite as

Boaz Barak and Kunal Marwaha. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.ITCS.2022.14,
  author =	{Barak, Boaz and Marwaha, Kunal},
  title =	{{Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.14},
  URN =		{urn:nbn:de:0030-drops-156105},
  doi =		{10.4230/LIPIcs.ITCS.2022.14},
  annote =	{Keywords: approximation algorithms, QAOA, maximum cut, local distributions}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.60
Memory-Sample Lower Bounds for Learning Parity with Noise

Authors: Sumegha Garg, Pravesh K. Kothari, Pengda Liu, and Ran Raz

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

Abstract
In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x = (x₁,…,x_n) ∈ {0,1}ⁿ from a stream of random linear equations over 𝔽₂ that are correct with probability 1/2+ε and flipped with probability 1/2-ε (0 < ε < 1/2), that any learning algorithm requires either a memory of size Ω(n²/ε) or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [Garg et al., 2018], when the samples are noisy. A matrix M: A × X → {-1,1} corresponds to the following learning problem with error parameter ε: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a₁, b₁), (a₂, b₂) …, where for every i, a_i ∈ A is chosen uniformly at random and b_i = M(a_i,x) with probability 1/2+ε and b_i = -M(a_i,x) with probability 1/2-ε (0 < ε < 1/2). Assume that k,𝓁, r are such that any submatrix of M of at least 2^{-k} ⋅ |A| rows and at least 2^{-𝓁} ⋅ |X| columns, has a bias of at most 2^{-r}. We show that any learning algorithm for the learning problem corresponding to M, with error parameter ε, requires either a memory of size at least Ω((k⋅𝓁)/ε), or at least 2^{Ω(r)} samples. The result holds even if the learner has an exponentially small success probability (of 2^{-Ω(r)}). In particular, this shows that for a large class of learning problems, same as those in [Garg et al., 2018], any learning algorithm requires either a memory of size at least Ω(((log|X|)⋅(log|A|))/ε) or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Ran Raz, 2017; Garg et al., 2018] to the noisy case.
Cite as

Sumegha Garg, Pravesh K. Kothari, Pengda Liu, and Ran Raz. Memory-Sample Lower Bounds for Learning Parity with Noise. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 60:1-60:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX/RANDOM.2021.60,
  author =	{Garg, Sumegha and Kothari, Pravesh K. and Liu, Pengda and Raz, Ran},
  title =	{{Memory-Sample Lower Bounds for Learning Parity with Noise}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{60:1--60:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.60},
  URN =		{urn:nbn:de:0030-drops-147534},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.60},
  annote =	{Keywords: memory-sample tradeoffs, learning parity under noise, space lower bound, branching program}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.23
A Stress-Free Sum-Of-Squares Lower Bound for Coloring

Authors: Pravesh K. Kothari and Peter Manohar

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We prove that with high probability over the choice of a random graph G from the Erdős-Rényi distribution G(n, 1/2), a natural n^{O(ε² log n)}-time, degree O(ε² log n) sum-of-squares semidefinite program cannot refute the existence of a valid k-coloring of G for k = n^{1/2 + ε}. Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovász theta function) cannot be appreciably improved by a natural o(log n)-degree sum-of-squares strengthening, and this is tight up to a n^{o(1)} slack in k. To the best of our knowledge, this is the first lower bound for coloring G(n, 1/2) for even a single round strengthening of the basic SDP in any SDP hierarchy. Our proof relies on a new variant of instance-preserving non-pointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [Boaz Barak et al., 2016; S. B. {Hopkins} et al., 2017; Dmitriy Kunisky and Afonso S. Bandeira, 2019; Mrinalkanti Ghosh et al., 2020; Mohanty et al., 2020]. Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.
Cite as

Pravesh K. Kothari and Peter Manohar. A Stress-Free Sum-Of-Squares Lower Bound for Coloring. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kothari_et_al:LIPIcs.CCC.2021.23,
  author =	{Kothari, Pravesh K. and Manohar, Peter},
  title =	{{A Stress-Free Sum-Of-Squares Lower Bound for Coloring}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.23},
  URN =		{urn:nbn:de:0030-drops-142978},
  doi =		{10.4230/LIPIcs.CCC.2021.23},
  annote =	{Keywords: Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.21
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG

Authors: Sumegha Garg, Pravesh K. Kothari, and Ran Raz

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

Abstract
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. Our first result applies to the problem of distinguishing the uniform distribution on {0,1}ⁿ from uniform distribution on some unknown linear subspace of {0,1}ⁿ. As a specific corollary, we show that any algorithm that distinguishes between uniform distribution on {0,1}ⁿ and uniform distribution on an n/2-dimensional linear subspace of {0,1}ⁿ with non-negligible advantage needs 2^Ω(n) samples or Ω(n²) memory (tight up to constants in the exponent). Our second result applies to distinguishing outputs of Goldreich’s local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich’s pseudorandom generator G fixes a predicate P:{0,1}^k → {0,1} and a collection of subsets S₁, S₂, …, S_m ⊆ [n] of size k. For any seed x ∈ {0,1}ⁿ, it outputs P(x_S₁), P(x_S₂), …, P(x_{S_m}) where x_{S_i} is the projection of x to the coordinates in S_i. We prove that whenever P is t-resilient (all non-zero Fourier coefficients of (-1)^P are of degree t or higher), then no algorithm, with < n^ε memory, can distinguish the output of G from the uniform distribution on {0,1}^m with a large inverse polynomial advantage, for stretch m ≤ (n/t) ^{(1-ε)/36 ⋅ t} (barring some restrictions on k). The lower bound holds in the streaming model where at each time step i, S_i ⊆ [n] is a randomly chosen (ordered) subset of size k and the distinguisher sees either P(x_{S_i}) or a uniformly random bit along with S_i. An important implication of our second result is the security of Goldreich’s generator with super linear stretch (in the streaming model), against memory-bounded adversaries, whenever the predicate P satisfies the necessary condition of t-resiliency identified in various prior works. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups). Our key technical contribution is to adapt this machinery to work for distinguishing problems in contrast to prior works on similar results for search/learning problems.
Cite as

Sumegha Garg, Pravesh K. Kothari, and Ran Raz. Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX/RANDOM.2020.21,
  author =	{Garg, Sumegha and Kothari, Pravesh K. and Raz, Ran},
  title =	{{Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.21},
  URN =		{urn:nbn:de:0030-drops-126248},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.21},
  annote =	{Keywords: memory-sample tradeoffs, bounded storage cryptography, Goldreich’s local PRG, distinguishing problems, refuting CSPs}
}
  • Refine by Author
  • 9 Kothari, Pravesh K.
  • 2 Barak, Boaz
  • 2 Garg, Sumegha
  • 2 Hsieh, Jun-Ting
  • 2 Manohar, Peter
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Lower bounds and information complexity
  • 2 Theory of computation → Semidefinite programming
  • 2 Theory of computation → Sparsification and spanners
  • 1 Mathematics of computing → Hypergraphs
  • Show More...

  • Refine by Keyword
  • 2 Sum-of-Squares
  • 2 approximation algorithm
  • 2 approximation algorithms
  • 2 memory-sample tradeoffs
  • 1 Asymmetric Group Steiner Tree
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 6 2024
  • 4 2023
  • 2 2019
  • 2 2020
  • 2 2021
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact