New answers tagged

2 votes

Why do almost all points in the unit interval have Kolmogorov complexity 1?

By the Point-to-Set principle (Lutz & Lutz 2018), for any $\varepsilon$ the set of real numbers with Kolmogorov complexity at most $\varepsilon$ has Hausdorff dimension $\varepsilon$. As $\mathbb{...
  • 3,629
20 votes
Accepted

Why do almost all points in the unit interval have Kolmogorov complexity 1?

I'm not an expert on Kolmogorov complexity, but this does seem like a counting argument: for any fixed $\epsilon > 0$, there are only $\sum_{i = 1}^{(1-\epsilon)n} 2^i < 2^{(1-\epsilon)n+1}$ ...
1 vote
Accepted

How to find the maximum of a sum of squares of sums?

You can solve the problem via binary quadratic programming as follows. Let binary decision variable $x_{id}$ indicate whether row $i$ is rotated $d$ places. The problem is to maximize $$\sum_{j=0}^{...
  • 4,088
4 votes

Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

Just adding some brief clarification to Carlo's answer. The randomness in the randomized constructions is used solely to randomly produce a lattice that satisfies certain properties. In particular, ...
  • 1,033
9 votes
Accepted

Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

The NP-hardness of the shortest vector problem in $L_2$ norm is discussed in this 2015 lecture by Vinod Vaikuntanathan. An algorithm for this problem would give a randomised algorithm for any problem ...
1 vote
Accepted

Computational complexity and commuting functions, examples and conjectures

This is not a proper answer. I will give a construction of a pair of functions $f,g$ assuming the access to some cryptographic function $e$ that probably should form a counterexample for Proposition ...

Top 50 recent answers are included