# All Questions

15 views

### Approximation algorithm for finding the maximum common subgraph in two directed graphs?

Suppose we have two directed graphs, $A$ and $B$ and we look to find the biggest subgraph that is common to both graphs. That is to find the biggest graph which is a subgraph of both $A$ and $B$. The ...
8 views

### Confusion related to derivation of CRF log likelihood gradient

I was reading this paper related to CRF and ran across the parameter estimation where they take the gradient of the log likelihood with respect to the parameters where $l$ is the log likelihood. ...
76 views

### What should I do to switch from math department to cs to research tcs topics?

This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first. I'm now a math student of master ...
13 views

### Grammars for matching properties of a left and right half of a string

I know that w#w is not a context-free language, but what about {xy | where |x| = |y|, x contains the same number of as as y [and therefore the same number of bs]}.
52 views

### Undecidability of whether a given TM has only mechanically detectable loops or always halts

This might be a bit of an abstruse question, but it's something I've been trying to prove. I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
117 views

### Is the D-Wave architecture a close implementation of quantum interactive proof?

A very high level architecture is, as mentioned here, shown in this picture. The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is ...
18 views

### Confusion related to minimization of a gaussian likelihood function

I have this confusion related to minimization of gaussian likelihood function. The negative of the log likelihood of gaussian distribution is $-logdet(Q) + tr(SQ) + \lambda||Q||_{1}$ where Q is the ...
31 views

### how to prove this unsolvable problem about halting problem (turing machine) [migrated]

Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
87 views

### Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
51 views

### Ergodic Theory and Hash Functions

I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, ...
30 views

### Why does Shellsort work well on Sorted and Reverse ordered lists? [migrated]

I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists. ...
61 views

### Number of accepting path of a non deterministic automaton

I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper. I have got a ...
47 views

### loop invariants in proving program termination

consider two similar pieces of (pseudo)code: A: n = f(x) for (i = 1 to n) do begin .... end B: x = 1 while (x != 0) do begin x = g(x) .... end in case A if ...
95 views

Background: I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, ...
45 views

### Start using SAT Solvers [migrated]

What i actually want to do is to turn a math problem ,i have to solve,to a Boolean Satisfiability problem and solve it using a SAT Solver. I wonder if someone knows any manual,guide or anything that ...
39 views

### Determination of maximum number of incoming transitions to a state in any trace-equivalent representation of an LTS

Suppose $L$ is a labelled transition system (LTS). Suppose that the function $maxIn(L)$ (LTS $\rightarrow$ integer) returns the number of incoming transitions to the state of $L$ that has the most ...
71 views

### The sum of all integers less than n with a zero [migrated]

For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703 In this problem, n is smaller than $10^{18}$ , and the algorithm should ...
83 views

### Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices

Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and ...
57 views

### Verifying the minimum degree of a geometric predicate

Let $F = (f_1, \ldots, f_n)$ be a sequence of multivariate polynomials $f_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function. Say the composition ...
98 views

17 views

### Are all databases reducible to this ultimate abstract database design? [migrated]

I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
76 views

### Breaking secure pseudorandom generators by assuming BPP != P

Suppose we find some problem X that is in BPP but not in P. Also, suppose we have access to a random oracle R. Do X and R allow us to break any claimed secure pseudo-random number generator? (Note ...
83 views

### Graph Has Two / Three Different Minimal Spanning Trees?

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
79 views

### Density of Ramsey Graphs

Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with ...
143 views

### Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication. It is known that the determinant of an $n\times n$ matrix can ...
65 views

### η-conversion vs extensionality in extensions of lambda-calculus

I'm often confused by the relation between η-conversion and extensionality. In the untyped lambda-calculus, the eta-rule gives the same proof system as the extensionality rule, as proven by ...
14 views

### nu-based Support Vector Machine (SVM): limit on nu for 1-class SVM?

For a nu-based SVM, there are limits on acceptable nu (soft margin) parameters (p. 126 of Appl. Stochastic Models Bus. Ind., 2005; 21:111–136). Are there similar limits on the nu parameter in the ...
173 views