Questions tagged [succinct]
The succinct tag has no usage guidance.
21 questions
1
vote
2
answers
162
views
Encoding of nodes in Binary Decision Diagrams
A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 12 bytes per node, with an additional 4 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple ...
- 1
2
votes
0
answers
185
views
Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?
There are $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$ possible $n$-element subsets of a $2n$-element set. Therefore, any data structure storing such a set must use at least $2n - O(\...
- 12.4k
1
vote
0
answers
73
views
Is there a succinct representation of factoring which remains computationally intractable?
I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
- 403
47
votes
0
answers
1k
views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
CommunityBot
- 1
3
votes
0
answers
93
views
Succinct problems over uniform computational models
For a language $\Pi$, the traditional definition of "Succinct-$\Pi$" is the set of encodings of circuits whose truth tables are members of $\Pi$.
This definition is essentially restricted (...
- 1,234
5
votes
0
answers
106
views
Data structures to store monotone functions
I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$:
$$
\forall x \in X: 0 \le x \le N\\
f: X \to \mathbb N\\
\forall x,y\in X:\quad x<...
- 151
3
votes
1
answer
178
views
CNF encoding of set cover - NExpTime-completness
Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.
I ...
CommunityBot
- 1
2
votes
0
answers
180
views
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 ...
- 337
14
votes
0
answers
475
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 119
4
votes
0
answers
112
views
A succinct version of permanent that is $EXP$-complete
Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete.
Permanent mod $2$ is in $\oplus L$ and so succinct version is ...
- 13.3k
6
votes
1
answer
569
views
On succinct $EXP$ and $NEXP$ complete problems?
We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems. ...
- 38.5k
1
vote
0
answers
149
views
Information theoretic lower-bound on object graph serialization
This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
- 12k
9
votes
0
answers
199
views
Is there a counting complexity class for succint problems?
Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving ...
CommunityBot
- 1
1
vote
0
answers
100
views
What is the name of this data structure? (hash table with a limit on the number of entries)
Denote $[n] \triangleq \{1,2,\ldots,n\}$.
Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, ...
- 9,508
7
votes
1
answer
231
views
Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space
A dynamic predecessor data structure supporting findPredecessor, insert, and delete over ...
- 11.2k
6
votes
0
answers
120
views
Practical algorithms for finding small arithmetic circuits
I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials. I am interested in practical (though obviously exponential time) ...
- 3,313
21
votes
3
answers
1k
views
Using Kolmogorov complexity as input "size"
Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some ...
- 7,788
9
votes
1
answer
429
views
Who coined the term "empirical entropy"?
I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis.
Shannon defined the entropy of ...
- 500
3
votes
1
answer
289
views
Succinct Representation and Communication complexity
Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$...
- 39
4
votes
2
answers
259
views
Dynamic and/or practical succinct data structures for triangulations
Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently?
Does anybody know of practical ...
CommunityBot
- 1
5
votes
0
answers
143
views
Succinct graphs with ability to perform random walk
Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex ...
- 2,806