# Time complexity of Succinct-CVP

I want to know what is the best known lower time complexity of Succinct-CVP? The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of the local reductions). If we expand the circuit then we have an $$2^n$$ size CVP which is decidable in time $$2^n$$. I searched a lot to find a better algorithm for this problem I was looking for $$2^{n/{\log^5 n}}$$ time algorithm but I can't even find an algorithm with time complexity of $$2^{n/3}$$. So I want to know is there any research around this problem or a better algorithm?

Succinct-CVP: given a circuit $$D(y_1,y_2,...,y_n)$$ that is a succinct description of a circuit $$C(x_1,x_2,...,x_n)$$ of size at most $$2^n$$ and an input $$a \in \{0,1\}^n$$, Compute the value $$C(a)$$.

• Should be Exp-complete. I found some notes here but you might need to search a bit to find the reference: users.cs.duke.edu/~reif/courses/complectures/Umans/lec2c.pdf Jul 18, 2020 at 9:40
• @BartoszBednarczyk Thank you. I know there is an $O(2^n)$ time algorithm for the problem but I think there should be better algorithms. I want to find an optimized algorithm. Jul 18, 2020 at 10:00
• But you were asking about the lower bound. What exactly is your question? Are you asking e.g. if you need (1,425285712)^n steps to solve the problem? Jul 18, 2020 at 14:28
• @BartoszBednarczyk $1.4^n$ is good and $2^{n/(\log^5 n)}$ is great. Jul 19, 2020 at 4:34
• So please update your question accordingly. Jul 20, 2020 at 7:32