More Like this

1. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.54  

   Allender, Eric ; Gouwar, John ; Hirahara, Shuichi ; Robelle, Caleb ( November 2021 , Leibniz international proceedings in informatics)

   Ahn, Hee-Kap ; Sadakane, Kunihiko (Ed.)

   A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing reductions; neither is known to be NP-complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P) under nonuniform ≤^{NC^0}_m reductions. In this paper, we improve this, to show that the complement of MKTP is hard for the (apparently larger) class NISZK_L under not only ≤^{NC^0}_m reductions but even under projections. Also, the complement of MKTP is hard for NISZK under ≤^{P/poly}_m reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK_L is the non-interactive version of the class SZK_L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP). 

   more » « less
2. On the connectivity of proper colorings of random graphs and hypergraphs

   https://doi.org/10.1002/rsa.20912  

   Anastos, Michael ; Frieze, Alan ( February 2020 , Random Structures & Algorithms)

   Let Ω_q=Ω_q(H) denote the set of proper [q]‐colorings of the hypergraphH. Let Γ_qbe the graph with vertex set Ω_qwhere two coloringsσ,τare adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH=H_n,m;k, k ≥ 2, the randomk‐uniform hypergraph withV=[n] andm=dn/khyperedges then w.h.p. Γ_qis connected ifdis sufficiently large and. This is optimal up to the first order ind. Furthermore, with a few more colors, we find that the diameter of Γ_qisO(n) w.h.p., where the hidden constant depends ond. So, with this choice ofd,q, the natural Glauber dynamics Markov Chain on Ω_qis ergodic w.h.p.

    

   more » « less
3. On One-way Functions and Kolmogorov Complexity

   Liu, Yanyi ; Pass, Rafael ( January 2020 , IEEE Symposium on Foundations of Computer Science (FOCS))

   null (Ed.)

   We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n) ≥ (1 + ε)n, ε > 0, the following are equivalent: • One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); • t-time bounded Kolmogorov Complexity, Kt, is mildly hard-on-average (i.e., there exists a polynomial p(n) > 0 such that no PPT algorithm can compute Kt, for more than a 1 − 1/p(n) fraction of n-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography. 

   more » « less
4. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

   Lu, Zhenjian ; Oliveira, Igor C. ; Zimand, Marius ( January 2022 , 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))

   Mikołaj Bojańczyk and Emanuela Merelli and David P. Woodruff (Ed.)

   The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then K(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [31] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [31], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) · log(1/δ) +O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 − o(1)) · log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. • Optimal coding theorem for pKt and unconditional Antunes-Fortnow. We consider pKt complexity [17], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pKt, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [5] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions. 

   more » « less
5. Sum-of-Squares Lower Bounds for Densest k-Subgraph

   https://doi.org/10.1145/3564246.3585221  

   Jones, Chris ; Potechin, Aaron ; Rajendran, Goutham ; Xu, Jeff ( June 2023 , STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing)

   Given a graph and an integer k, Densest k-Subgraph is the algorithmic task of finding the subgraph on k vertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The state-of-the-art algorithm is an O(n^{1/4+ϵ})-factor approximation (for any ϵ>0) due to Bhaskara et al. [STOC '10]. Moreover, the so-called log-density framework predicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve an O(n^{1/4−ϵ})-factor approximation. In the average case, Densest k-Subgraph is a prototypical noisy inference task which is conjectured to exhibit a statistical-computational gap. In this work, we provide the strongest evidence yet of hardness for Densest k-Subgraph by showing matching lower bounds against the powerful Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming that achieves state-of-art algorithmic guarantees for many optimization and inference problems. For k ≤ n^1/2, we obtain a degree n^δ SoS lower bound for the hard regime as predicted by the log-density framework. To show this, we utilize the modern framework for proving SoS lower bounds on average-case problems pioneered by Barak et al. [FOCS '16]. A key issue is that small denser-than-average subgraphs in the input will greatly affect the value of the candidate pseudo-expectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on the positive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small. 

   more » « less