0
votes
0answers
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 ...
0
votes
0answers
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. ...
2
votes
0answers
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 ...
-4
votes
0answers
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]}.
-1
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
-3
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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$, ...
-1
votes
0answers
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.
...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
5
votes
1answer
95 views
Resources for mathematicians hoping to learn more computer science
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, ...
-4
votes
0answers
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 ...
2
votes
0answers
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 ...
-4
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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
...
3
votes
1answer
98 views
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf ...
-3
votes
0answers
25 views
Cohen Sutherland line clipping algorithm [closed]
using Cohen Sutherland line clipping algorithm clip the line form (-3/2,1) to (3/2,2) against the window: (-1,-1),(-1,1), (1,-1),(1,1)
5
votes
1answer
110 views
Does a chordal graph where the size of minimal separators is constrained have name?
An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains ...
8
votes
0answers
133 views
Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?
(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
-2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
8
votes
1answer
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 ...
8
votes
2answers
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 ...
7
votes
0answers
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 ...
0
votes
0answers
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 ...
4
votes
1answer
173 views
On the proof of Meyer's Theorem
Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} ...
1
vote
0answers
46 views
Simulating alternating Turing Machines with bounded alternations by a deterministic Turing Machine
Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice versa) that works in polynomial space.
...
1
vote
1answer
46 views
partition to min the max number of intersections
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
-1
votes
0answers
31 views
Bound on vertex heights in Push-Relabel
I'm having a little bit of trouble understanding Lemma 26.20 in CLRS 3rd Edition. It states that on a graph $G=(V,E)$, $\forall v \in V, h(v) \leq 2|V| - 1$. I can see the intuition behind the proof, ...
-1
votes
0answers
10 views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word [migrated]
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
-2
votes
0answers
46 views
Adaboost with basic Linear Classifier
I am trying to implement the adaboost algorithm with the simple linear classifier as weak learner. For this I am using the pseudo inverse rule. i.e. w = inv(X*X')*X*t, where w is the weight vector of ...
6
votes
0answers
143 views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
0
votes
0answers
83 views
Is there a way to transform a Turing machine into an oblivious turing machine that decides the same langauage?
Suppose you have turing machine M that decides L. Is there a simple way to convert this turing machine into an oblivious turing machine M' that decides the same language? My intuition says yes but i ...
2
votes
1answer
93 views
Inferring simplest method to convert bit array 1 to bit array 2
Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.
Now select a single function out of the latter set. Is there any ...
-4
votes
0answers
24 views
Proof that the regular languages are closed under string homomorphism [migrated]
Where can I find a proof of this? Thanks!
0
votes
1answer
45 views
The meaning of: a program P posseses a property R
I am reading an article called The temporal semantics of concurrent programs
.
A construction is then given for assigning to a program P a temporal
formula W(P) which is true on all proper ...
20
votes
2answers
423 views
Wikipedia-style explanation of Geometric Complexity Theory
Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the ...
4
votes
1answer
77 views
Understanding the “gap theorem” in geometric spanners
I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:
Intuitively: A set of directed edges satisfies the gap property, if ...
3
votes
1answer
100 views
Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$
Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ ...
-4
votes
0answers
39 views
What do these Codes mean? [closed]
Code 1-
public void actionPerformed(ActionEvent e) {
if (inGame) {
checkApple();
checkCollision();
move();
}
repaint();
}
--------------------------------------…
Code 2-
public void ...
2
votes
1answer
80 views
Locally monotone Boolean function
I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40:
A function $f$ is ...
8
votes
0answers
115 views
Smoothed analysis of approximation algorithms
Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
3
votes
0answers
62 views
Stronger version of Isolation Lemma for linear forms
Klivans and Spielman give isolation lemma for linear forms in their paper Randomness Efficient Identity Testing of Multivariate Polynomials. Lemma 4 in this paper says.
"Let $C$ be any collection ...
0
votes
0answers
52 views
Intersection of N rectangles and M points
There are N rectangles parallel to X and Y axis and they do not overlap, also there are M points. For each point find an enclosing rectangle (or absence of one). Total runtime complexity should be not ...
2
votes
0answers
51 views
concurrent non-malleable *statistical* zero knowledge
According to Huijia Lin and
Rafael Pass's "Concurrent Non-Malleable Zero Knowledge with
Adaptive Inputs" paper:
if collision-resistant hash functions exist, then
"there exists a ...
