# Tag Info

Accepted

• 37.4k

### Easy problems with hard counting versions

From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point From the abstract: This is the only natural computational problem where determining the existence of an object (...
• 6,011

### How to check if a number is a perfect power in polynomial time

Somehow, I can show that the binary search algorithm is $O(lg~n \cdot (lg~lg~n)^2)$. Firstly, $a^b = n$, there is $b<lg~n$. Binary Search Algorithm: For each $b$, we use binary search to find ...
• 141

### Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

If you know that the $a_i$'s are all not too large, and you have a good approximation to $f(a_0,\dots,a_n)$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the ...
• 12.2k

### Algorithm to check whether a given set is Sidon

In what range are the values in your set $S$? Note that if the range is not too large you can represent $S$ by a polynomial $P_S$ ($P_S = \sum_{s \in S} x^s$) and compute $P_S^{2}$ with the FFT ...

### Base-k representations of the co-domain of a polynomial - is it context-free?

I think I have a proof. The proof follows from this lemma. Lemma. For a context-free language $L$ if for infinitely many $n$ there are $n^6$ words of equal length whose first $n^2$ letters are the ...
• 14k

### Base-k representations of the co-domain of a polynomial - is it context-free?

This is a sketch of the proof for $k=2$ and $L = \{[n^2]_2 \mid n \geq 1\}$; where $[n^2]_2$ is the binary representation of $n^2$. For better clarity we place the least significant bit of the binary ...

### Analytic Number theory in TCS

Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/...
Accepted

### Relation between transcendental numbers and computational complexity?

One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number ...
• 37.4k

### Is there a natural problem on the naturals that is NP-complete?

Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from ...
• 812