Tag Info

2

The manufacturers of the computing hardware themselves are their own customers, and use supercomputing to approximatively solve a number of well-know and more obscure NP-hard tasks. One of the oldest and best-known is place-and-route, a short overview of electronic design automation reveals many more NP-hard tasks. Often the employed algorithms are true NP ...

5

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs. For a lower bound, consider formula $F$ with $n$ inputs ...

3

If you allow the graphs to be disconnected, then there are no good upper bounds, with respect to the number of vertices. For $r$-regular graphs take the disjoint union of $l$ complete graphs $K_{r+1}$. Then the graph has $(r+1)\cdot l$ vertices, and $(r+1)!\cdot l!$ automorphisms.

2

The algorithm described by Frederickson and Johnson in 1982 considers that all sets have the same size. They also described in 1980 an optimal solution that takes advantage of the different sizes of the sorted sets. The complexity of this algorithm is within $O(k + \sum^k_{i=1}\log{n_i})$. Reference Greg N. Frederickson and Donald B. Johnson. 1980. ...

6

There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error ...

2

Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \mathbb N$ such that $T^{(k)}(n)=1$. If instead of $T(n)=n+1$ when $n$ is odd, we had defined $T(n)=3n+1$ when $n$ is odd, we would have the Collatz Conjecture, ...

1

Algebraic Geometry Algebraic Geometry by Robin Hartshorne. The book is, for me, challenging but covers a broad area of the field of algebraic geometry. I found this a good addition to the next book when learning about ellipc curve cryptography. Elliptic curves The Arithmetic of Elliptic Curves by Joseph H. Silverman. The book is a good introduction ...

5

In many nonuniform models - Boolean circuits, algebraic circuits, decision trees, branching programs, etc. - computing exact complexity seems to be significantly harder than computing asymptotic complexity. While I maintain hope that your intuition is correct - that understanding exact complexity of small instances might lead to asymptotic insights - I know ...

7

Yes, this is a natural idea and people have thought about it. In short, the problem is that even the state-of-the-art SAT/QBF-solvers allow to find very small circuits only (with about 10–12 gates), not to say about proving that there is no small circuit. Some references: Ryan Williams, Applying practice to theory (2008): Our knowledge of ...

1

The k=2 case comes up in parallel merge sort since the merging of two sorted arrays from different threads needs to be split up among two threads to maintain the same amount of parallelism. This homework solution is one reference.

3

Combinatorial game theory plays a role in logic and computer science as in, for example, the Ehrenfeucht-fraïssé game, which is a logic game played on model-theoretic structures. At each turn, the first player chooses an element from one of the two structures, and the second has to chose an element from the other, trying to maintain a local isomorphisms ...

9

My favorite resource for this subject is the book Sparsity by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always the Wikipedia article.

1

SAT-solvers are another common class of heuristics. There are many and of course they take exponential time in the worst case. My suggestion is to explain to the reviewers that the problem is NP-complete and cannot be solved or approximated in less than exponential time if there are such results. That should suffice if your algorithm outperforms the best ...

3

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential. Two canonical examples are the simplex algorithm for linear programming ...

0

As I understand your algorithm, whether or not the worst-case running time is exponential does not depend on the size of the search space. If the number of different possible solution values happened to be upper bounded by a polynomial in the input size, then the complexity of your heuristic would be polynomial, too. This is true for many canonical NP-hard ...

Top 50 recent answers are included