33 Search Results for "Koucky, Michal"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.51
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

Authors: Halley Goldberg and Valentine Kabanets

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

Abstract
A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK^{t}P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, we give consequences of randomized NP-hardness reductions for both approximating and exactly computing time-bounded and time-unbounded Kolmogorov complexity. In the setting of approximate K^{poly} complexity, our results are as follows. 1) Under a derandomization assumption, for any constant δ > 0, if approximating K^t complexity within n^{δ} additive error is hard for SAT under an honest randomized non-adaptive Turing reduction running in time polynomially less than t, then NP = coNP. 2) Under the same assumptions, the worst-case hardness of NP is equivalent to the existence of one-way functions. Item 1 above may be compared with a recent work of Saks and Santhanam [Michael E. Saks and Rahul Santhanam, 2022], which makes the same assumptions except with ω(log n) additive error, obtaining the conclusion NE = coNE. In the setting of exact K^{poly} complexity, where the barriers of Item 1 and [Michael E. Saks and Rahul Santhanam, 2022] do not apply, we show: 3) If computing K^t complexity is hard for SAT under reductions as in Item 1, then the average-case hardness of NP is equivalent to the existence of one-way functions. That is, "Pessiland" is excluded. Finally, we give consequences of NP-hardness of exact time-unbounded Kolmogorov complexity under randomized reductions. 4) If computing Kolmogorov complexity is hard for SAT under a randomized many-one reduction running in time t_R and with failure probability at most 1/(t_R)^16, then coNP is contained in non-interactive statistical zero-knowledge; thus NP ⊆ coAM. Also, the worst-case hardness of NP is equivalent to the existence of one-way functions. We further exploit the connection to NISZK along with a previous work of Allender et al. [Eric Allender et al., 2023] to show that hardness of K complexity under randomized many-one reductions is highly robust with respect to failure probability, approximation error, output length, and threshold parameter.
Cite as

Halley Goldberg and Valentine Kabanets. Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.APPROX/RANDOM.2024.51,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{51:1--51:19},
  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.51},
  URN =		{urn:nbn:de:0030-drops-210444},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.51},
  annote =	{Keywords: Meta-complexity, Randomized reductions, NP-hardness, Worst-case complexity, Time-bounded Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.5
On the Power of Adaptivity for Function Inversion

Authors: Karthik Gajulapalli, Alexander Golovnev, and Samuel King

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We study the problem of function inversion with preprocessing where, given a function f : [N] → [N] and a point y in its image, the goal is to find an x such that f(x) = y using at most T oracle queries to f and S bits of preprocessed advice that depend on f. The seminal work of Corrigan-Gibbs and Kogan [TCC 2019] initiated a line of research that shows many exciting connections between the non-adaptive setting of this problem and other areas of theoretical computer science. Specifically, they introduced a very weak class of algorithms (strongly non-adaptive) where the points queried by the oracle depend only on the inversion point y, and are independent of the answers to the previous queries and the S bits of advice. They showed that proving even mild lower bounds on strongly non-adaptive algorithms for function inversion would imply a breakthrough result in circuit complexity. We prove that every strongly non-adaptive algorithm for function inversion (and even for its special case of permutation inversion) must have ST = Ω(N log (N) log (T)). This gives the first improvement to the long-standing lower bound of ST = Ω(N log N) due to Yao [STOC 90]. As a corollary, we conclude the first separation between strongly non-adaptive and adaptive algorithms for permutation inversion, where the adaptive algorithm by Hellman [TOIT 80] achieves the trade-off ST = O(N log N). Additionally, we show equivalence between lower bounds for strongly non-adaptive data structures and the one-way communication complexity of certain partial functions. As an example, we recover our lower bound on function inversion in the communication complexity framework.
Cite as

Karthik Gajulapalli, Alexander Golovnev, and Samuel King. On the Power of Adaptivity for Function Inversion. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.ITC.2024.5,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and King, Samuel},
  title =	{{On the Power of Adaptivity for Function Inversion}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.5},
  URN =		{urn:nbn:de:0030-drops-205137},
  doi =		{10.4230/LIPIcs.ITC.2024.5},
  annote =	{Keywords: Function Inversion, Non-Adaptive lower bounds, Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.22
The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension

Authors: Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
It is celebrated that a simple random walk on ℤ and ℤ² returns to the initial vertex v infinitely many times during infinitely many transitions, which is said recurrent, while it returns to v only finite times on ℤ^d for d ≥ 3, which is said transient. It is also known that a simple random walk on a growing region on ℤ^d can be recurrent depending on growing speed for any fixed d. This paper shows that a simple random walk on {0,1,…,N}ⁿ with an increasing n and a fixed N can be recurrent depending on the increasing speed of n. Precisely, we are concerned with a specific model of a random walk on a growing graph (RWoGG) and show a phase transition between the recurrence and transience of the random walk regarding the growth speed of the graph. For the proof, we develop a pausing coupling argument introducing the notion of weakly less homesick as graph growing (weakly LHaGG).
Cite as

Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22,
  author =	{Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki},
  title =	{{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22},
  URN =		{urn:nbn:de:0030-drops-204577},
  doi =		{10.4230/LIPIcs.AofA.2024.22},
  annote =	{Keywords: Random walk, dynamic graph, recurrence, transience, coupling}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.4
Derandomizing Logspace with a Small Shared Hard Drive

Authors: Edward Pyne

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

Abstract
We obtain new catalytic algorithms for space-bounded derandomization. In the catalytic computation model introduced by (Buhrman, Cleve, Koucký, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. We prove that BPSPACE[S] ⊆ CSPACE[S,S²] where BPSPACE[S] corresponds to randomized space S computation, and CSPACE[S,C] corresponds to catalytic algorithms that use O(S) bits of workspace and O(C) bits of catalytic space. Previously, only BPSPACE[S] ⊆ CSPACE[S,2^O(S)] was known. In fact, we prove a general tradeoff, that for every α ∈ [1,1.5], BPSPACE[S] ⊆ CSPACE[S^α,S^(3-α)]. We do not use the algebraic techniques of prior work on catalytic computation. Instead, we develop an algorithm that branches based on if the catalytic tape is conditionally random, and instantiate this primitive in a recursive framework. Our result gives an alternate proof of the best known time-space tradeoff for BPSPACE[S], due to (Cai, Chakaravarthy, and van Melkebeek, Theory Comput. Sys. 2006). As a final application, we extend our results to solve search problems in CSPACE[S,S²]. As far as we are aware, this constitutes the first study of search problems in the catalytic computing model.
Cite as

Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pyne:LIPIcs.CCC.2024.4,
  author =	{Pyne, Edward},
  title =	{{Derandomizing Logspace with a Small Shared Hard Drive}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{4:1--4:20},
  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.4},
  URN =		{urn:nbn:de:0030-drops-204006},
  doi =		{10.4230/LIPIcs.CCC.2024.4},
  annote =	{Keywords: Catalytic computation, space-bounded computation, derandomization}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.5
Explicit Time and Space Efficient Encoders Exist Only with Random Access

Authors: Joshua Cook and Dana Moshkovitz

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

Abstract
We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time n^{1 + o(1)} and space polylog(n) provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [Divsalar et al., 1998] and the codes described in [Gál et al., 2013]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length. In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access.
Cite as

Joshua Cook and Dana Moshkovitz. Explicit Time and Space Efficient Encoders Exist Only with Random Access. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.CCC.2024.5,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Explicit Time and Space Efficient Encoders Exist Only with Random Access}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{5:1--5:54},
  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.5},
  URN =		{urn:nbn:de:0030-drops-204015},
  doi =		{10.4230/LIPIcs.CCC.2024.5},
  annote =	{Keywords: Time-Space Trade Offs, Error Correcting Codes, Encoders, Explicit Constructions, Streaming Lower Bounds, Sequential Access, Time-Space Lower Bounds, Lossless Condensers, Invertible Condensers, Condensers}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.9
Lifting Dichotomies

Authors: Yaroslav Alekseev, Yuval Filmus, and Alexander Smal

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

Abstract
Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure A for some function f, we compose f with a carefully chosen gadget function g and get essentially the same lower bound on a complexity measure B for the lifted function f ⋄ g. Lifting theorems have a number of applications in many different areas such as circuit complexity, communication complexity, proof complexity, etc. One of the main question in the context of lifting is how to choose a suitable gadget g. Generally, to get better results, i.e., to minimize the losses when transferring lower bounds, we need the gadget to be of a constant size (number of inputs). Unfortunately, in many settings we know lifting results only for gadgets of size that grows with the size of f, and it is unclear whether it can be improved to a constant size gadget. This motivates us to identify the properties of gadgets that make lifting possible. In this paper, we systematically study the question "For which gadgets does the lifting result hold?" in the following four settings: lifting from decision tree depth to decision tree size, lifting from conjunction DAG width to conjunction DAG size, lifting from decision tree depth to parity decision tree depth and size, and lifting from block sensitivity to deterministic and randomized communication complexities. In all the cases, we prove the complete classification of gadgets by exposing the properties of gadgets that make lifting results hold. The structure of the results shows that there is no intermediate cases - for every gadget there is either a polynomial lifting or no lifting at all. As a byproduct of our studies, we prove the log-rank conjecture for the class of functions that can be represented as f ⋄ OR ⋄ XOR for some function f. In this extended abstract, the proofs are omitted. Full proofs are given in the full version [Yaroslav Alekseev et al., 2024].
Cite as

Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alekseev_et_al:LIPIcs.CCC.2024.9,
  author =	{Alekseev, Yaroslav and Filmus, Yuval and Smal, Alexander},
  title =	{{Lifting Dichotomies}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-204051},
  doi =		{10.4230/LIPIcs.CCC.2024.9},
  annote =	{Keywords: decision trees, log-rank conjecture, lifting, parity decision trees}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.11
Linear-Size Boolean Circuits for Multiselection

Authors: Justin Holmgren and Ron Rothblum

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

Abstract
We study the circuit complexity of the multiselection problem: given an input string x ∈ {0,1}ⁿ along with indices i_1,… ,i_q ∈ [n], output (x_{i_1},… ,x_{i_q}). A trivial lower bound for the circuit size is the input length n + q⋅log(n), but the straightforward construction has size Θ(q⋅n). Our main result is an O(n+q⋅log³(n))-size and O(log(n+q))-depth circuit for multiselection. In particular, for any q ≤ n/log³(n) the circuit has linear size and logarithmic depth. Prior to our work no linear-size circuit for multiselection was known for any q = ω(1) and regardless of depth.
Cite as

Justin Holmgren and Ron Rothblum. Linear-Size Boolean Circuits for Multiselection. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.CCC.2024.11,
  author =	{Holmgren, Justin and Rothblum, Ron},
  title =	{{Linear-Size Boolean Circuits for Multiselection}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{11:1--11:20},
  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.11},
  URN =		{urn:nbn:de:0030-drops-204070},
  doi =		{10.4230/LIPIcs.CCC.2024.11},
  annote =	{Keywords: Private Information Retrieval, Batch Selection, Boolean Circuits}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.36
Gap MCSP Is Not (Levin) NP-Complete in Obfustopia

Authors: Noam Mazor and Rafael Pass

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

Abstract
We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size Problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions. In more detail: - Assuming the existence of indistinguishability obfuscation, and subexponentially-secure one-way functions, an appropriate Gap version of MCSP is not NP-complete under randomized Levin-reductions. - Assuming the existence of subexponentially-secure indistinguishability obfuscation, subexponentially-secure one-way functions and injective PRGs, an appropriate Gap version of MKTP is not NP-complete under randomized Levin-reductions.
Cite as

Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36,
  author =	{Mazor, Noam and Pass, Rafael},
  title =	{{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{36:1--36:21},
  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.36},
  URN =		{urn:nbn:de:0030-drops-204322},
  doi =		{10.4230/LIPIcs.CCC.2024.36},
  annote =	{Keywords: Kolmogorov complexity, MCSP, Levin Reduction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.13
Learning Low-Degree Quantum Objects

Authors: Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos

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

Abstract
We consider the problem of learning low-degree quantum objects up to ε-error in 𝓁₂-distance. We show the following results: (i) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (ii) polynomials p:{-1,1}ⁿ → [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d ⋅ log n) many random examples (x,p(x)) (which implies learnability even for d = O(log n)), and (iii) degree-d polynomials p:{-1,1}ⁿ → [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary U_p that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.
Cite as

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos. Learning Low-Degree Quantum Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2024.13,
  author =	{Arunachalam, Srinivasan and Dutt, Arkopal and Escudero Guti\'{e}rrez, Francisco and Palazuelos, Carlos},
  title =	{{Learning Low-Degree Quantum Objects}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{13:1--13: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.13},
  URN =		{urn:nbn:de:0030-drops-201563},
  doi =		{10.4230/LIPIcs.ICALP.2024.13},
  annote =	{Keywords: Tomography}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.24
Exponential Lower Bounds via Exponential Sums

Authors: Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee

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

Abstract
Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale τ-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW⁰_{nb}[𝖯], assuming the same conjecture. VW⁰_{nb}[𝖯] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale τ-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial τ-complexity. Finally, we characterize a related class VW[𝖥], in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[𝖥] on certain types of graphs.
Cite as

Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee. Exponential Lower Bounds via Exponential Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ICALP.2024.24,
  author =	{Bhattacharjee, Somnath and Bl\"{a}ser, Markus and Dutta, Pranjal and Mukherjee, Saswata},
  title =	{{Exponential Lower Bounds via Exponential Sums}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-201677},
  doi =		{10.4230/LIPIcs.ICALP.2024.24},
  annote =	{Keywords: Algebraic complexity, parameterized complexity, exponential sums, counting hierarchy, tau conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.22
Streaming k-Edit Approximate Pattern Matching via String Decomposition

Authors: Sudatta Bhattacharya and Michal Koucký

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

Abstract
In this paper we give an algorithm for streaming k-edit approximate pattern matching which uses space Õ(k²) and time Õ(k²) per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya [Kociumaka et al., 2022] which uses space Õ(k⁵) and time Õ(k⁸) per arriving symbol. In the k-edit approximate pattern matching problem we get a pattern P and text T and we want to identify all substrings of the text T that are at edit distance at most k from P. In the streaming version of this problem both the pattern and the text arrive in a streaming fashion symbol by symbol and after each symbol of the text we need to report whether there is a current suffix of the text with edit distance at most k from P. We measure the total space needed by the algorithm and time needed per arriving symbol.
Cite as

Sudatta Bhattacharya and Michal Koucký. Streaming k-Edit Approximate Pattern Matching via String Decomposition. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ICALP.2023.22,
  author =	{Bhattacharya, Sudatta and Kouck\'{y}, Michal},
  title =	{{Streaming k-Edit Approximate Pattern Matching via String Decomposition}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{22:1--22:14},
  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.22},
  URN =		{urn:nbn:de:0030-drops-180741},
  doi =		{10.4230/LIPIcs.ICALP.2023.22},
  annote =	{Keywords: Approximate pattern matching, edit distance, streaming algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.54
The Hamilton Compression of Highly Symmetric Graphs

Authors: Petr Gregor, Arturo Merino, and Torsten Mütze

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We say that a Hamilton cycle C = (x₁,…,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁,…,x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.
Cite as

Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54,
  author =	{Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
  title =	{{The Hamilton Compression of Highly Symmetric Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.54},
  URN =		{urn:nbn:de:0030-drops-168529},
  doi =		{10.4230/LIPIcs.MFCS.2022.54},
  annote =	{Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.39
Data Structures Lower Bounds and Popular Conjectures

Authors: Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li [Li and Li, 2004] and several data structure problems such as non-adaptive function inversion of Hellman [M. Hellman, 1980] and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.
Cite as

Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.39,
  author =	{Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal and Kr\'{a}l, Karel and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Data Structures Lower Bounds and Popular Conjectures}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.39},
  URN =		{urn:nbn:de:0030-drops-146207},
  doi =		{10.4230/LIPIcs.ESA.2021.39},
  annote =	{Keywords: Data structures, Circuits, Lower bounds, Network Coding Conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.88
Sorting Short Integers

Authors: Michal Koucký and Karel Král

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We build boolean circuits of size 𝒪(nm²) and depth 𝒪(log(n) + m log(m)) for sorting n integers each of m-bits. We build also circuits that sort n integers each of m-bits according to their first k bits that are of size 𝒪(nmk (1 + log^*(n) - log^*(m))) and depth 𝒪(log³(n)). This improves on the results of Asharov et al. [Asharov et al., 2021] and resolves some of their open questions.
Cite as

Michal Koucký and Karel Král. Sorting Short Integers. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{koucky_et_al:LIPIcs.ICALP.2021.88,
  author =	{Kouck\'{y}, Michal and Kr\'{a}l, Karel},
  title =	{{Sorting Short Integers}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{88:1--88:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.88},
  URN =		{urn:nbn:de:0030-drops-141577},
  doi =		{10.4230/LIPIcs.ICALP.2021.88},
  annote =	{Keywords: sorting, small integers, boolean circuits}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.94
An Efficient Coding Theorem via Probabilistic Representations and Its Applications

Authors: Zhenjian Lu and Igor C. Oliveira

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A probabilistic representation of a string x ∈ {0,1}ⁿ is given by the code of a randomized algorithm that outputs x with high probability [Igor C. Oliveira, 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ensemble 𝒟_m can be uniformly sampled in time T(m) and generates a string x ∈ {0,1}^* with probability at least δ, then x admits a time-bounded probabilistic representation of complexity O(log(1/δ) + log (T) + log(m)). Under mild assumptions, a representation of this form can be computed from x and the code of the sampler in time polynomial in n = |x|. We derive consequences of this result relevant to the study of data compression, pseudodeterministic algorithms, time hierarchies for sampling distributions, and complexity lower bounds. In particular, we describe an instance-based search-to-decision reduction for Levin’s Kt complexity [Leonid A. Levin, 1984] and its probabilistic analogue rKt [Igor C. Oliveira, 2019]. As a consequence, if a string x admits a succinct time-bounded representation, then a near-optimal representation can be generated from x with high probability in polynomial time. This partially addresses in a time-bounded setting a question from [Leonid A. Levin, 1984] on the efficiency of computing an optimal encoding of a string.
Cite as

Zhenjian Lu and Igor C. Oliveira. An Efficient Coding Theorem via Probabilistic Representations and Its Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 94:1-94:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICALP.2021.94,
  author =	{Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{An Efficient Coding Theorem via Probabilistic Representations and Its Applications}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{94:1--94:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.94},
  URN =		{urn:nbn:de:0030-drops-141630},
  doi =		{10.4230/LIPIcs.ICALP.2021.94},
  annote =	{Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
  • Refine by Author
  • 13 Koucký, Michal
  • 4 Koucky, Michal
  • 3 Das, Debarati
  • 3 Dvořák, Pavel
  • 3 Loff, Bruno
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Computational complexity and cryptography
  • 3 Theory of computation → Pattern matching
  • 2 Theory of computation
  • 1 Computing methodologies → Representation of Boolean functions
  • 1 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 4 computational complexity
  • 3 Kolmogorov complexity
  • 3 derandomization
  • 2 Boolean circuits
  • 2 Catalytic computation
  • Show More...

  • Refine by Type
  • 33 document

  • Refine by Publication Year
  • 10 2024
  • 5 2021
  • 3 2017
  • 3 2019
  • 3 2020
  • 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