# Tag Info

1

The main credit should go to John Fearnley! Here is a PSPACE-complete problem given in (John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223): \mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n) \}, ...

2

Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min_{i,j} b_i/A_{i,j}$ (which we can assume is at least $1$). If $A$ ...

0

I think this problem is related to Hall's marriage theorem: Assuring that a bipartite graph $G=(A, B, E)$ contains a matching of $A$ if and only if each subset $S$ of $A$ has at least $|S|$ neighbors in $B$. Also your problem can be solved by the sparse connector design and the definition of it can be seen below: The sparse connector problem can be ...

3

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this. Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata ...

0

There is an elementary argument showing that a minimal NFA must have $O(|\Sigma|^k)$ states, so I guess the standard construction is essentially optimal. The argument is as follows. Suppose w.l.o.g. that $A$ is a NFA without $\epsilon$-transitions recognizing $L_k$. We can make the following assumptions: $A$ has a unique starting state $q_0$ and each state ...

11

Books: Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006. Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.) Articles: Alexander Razborov, "Communication Complexity". Lecture Notes: Toni Pitassi, "Communication Complexity, Information Complexity ...

1

Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.

4

I found the reference for CPO-like categories. Scott's paper Continuous Lattices in the book Toposes, Algebraic Geometry and Logic. It is explained in the comments right after corollary 4.3. A more general theorem can be found in Smyth's and Plotkin's paper Category-Theoretic Solution of Recursive Domain Equations. It is lemma 2. However, again, the ...

1

"Why ordinals are good for you" by I. Lepper and G. Moser. The paper itself is not intended to be humorous but it contains some funny quotes. I would be curious to see a similar introductory paper to the surreal numbers, a superclass of the ordinals introduced by J.H. Conway.

4

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems. EdgeCover is included in the dichotomy theorem in (1). Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs. To see ...

6

What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature? Suppose that you've implemented a shared memory machine $M$ that only satisfies eventual linearization, defined as follows: in every run $\alpha$ of $M$, there exists some point in time $T_\alpha$, such that linearization holds ...

5

Regarding your first question - safety properties are, in a way, the "easiest" properties to handle, with respect to problems such as model-checking and synthesis. The basic reason for this is that in the automata-theoretic approach to formal methods, reasoning about safety properties reduces to reasoning about finite traces, which is easier than the ...

0

heres an example PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS KAYAASLAN et al (there is also some research on hypergraph edge separators used in SAT solvers & other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)

2

I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment. But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts: "Large Alphabets and Incompressibility" by Travis Gagie (2008) "Emprical entropy" by ...

3

What about the following proof? If $\alpha(G) \leq \sqrt{n}$, then the claim holds obviously. Suppose the contrary, and let $I$ be an independent set of $G$ with maximum cardinality $\alpha$. Color $I$ with color 1, and recursively color the graph $G - I$ with colors $2,...,c$. Now, if $K$ is an independent set of $G$, consider $K' = K - I$. By induction ...

7

The following claim is known to me, but may not count because it is unpublished: Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors, where $B(B+1)\leq 2kn$. This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph ...

8

Not quite what you ask for, but here's a lower bound - a graph for which any coloring will result in an independent set colored by $\sqrt{n}$ colors: Take $\sqrt{n}$ copies of $K_{\sqrt{n}}$, and connect all vertices to a single vertex $s$. Obviously, every set of $\sqrt{n}$ vertices from different $K$'s is independent, and in every copy of $K_{\sqrt{n}}$ ...

1

While this doesn't answer your exact question, CFG parsing is a decision problem that was reduced from matrix multiplication (so it is as hard as matrix multiplication in a sense). Specifically, in [1] it was shown that CFG parsing is as hard as boolean matrix multiplication. In particular, if CFG parsing (a decision problem) can be solved in ...

3

There is another NP-Complete problem in the same spirit: for a square matrix to decide whether all its principal submatrices(i.e. rows and columns from the same set) are nonsingular. Another curious fact: sum of squares of determinants of all square submatrices is easy(just Det(I + AA^{T})), but the sum of absolute values is #P-Complete.

5

Yes, your problem is essentially equivalent to the one (General Position) in the Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran paper. Consider an $n \times m$ matrix $A$, $n < m$. Without loss of generality, assume that $\text{rank}(A) = n$ and the first $n$ columns of $A$ are independent: $A =[B\ |\ D]$, where $B$ is a nonsingular ...

14

There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in his book. A number of links have been found more recently as well, for example Kunal's blog post talks about the connection to differential privacy from [MN] and [NTZ]. Another example is Larsen's idea of using discrepancy to ...

2

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.

2

As pointed out in the comments, the power of such devices depends on the operations that they are allowed to perform on the ''register''. Here is a classic example of a class that captures all regular, but not all context-free languages. If you restrict a PDA so that there is only one stack symbol, apart from the bottom-of-the-stack, the device is called a ...

1

The following tech-report (a simplified version of an earlier paper by the same authors) on general BP (not only loopy-BP), but has fantastic insights. It's a great place to start, if you already haven't. http://www.merl.com/publications/docs/TR2001-22.pdf Another good place is this book: Information, Physics, and Computation - by Mezard and Montanari.

Top 50 recent answers are included