0
votes
0answers
22 views
Difference between Analytical and Difference Engines
I'm not sure if one can compare the two, mainly because what I've read so far, I didn't quite understand, but what are the key differences between these 2 engines?
-1
votes
0answers
17 views
What is the difference between Transitive Closure and Join? [migrated]
In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?
-4
votes
0answers
37 views
Using Little's law to find the average N of customers
I'm trying to understand Little's law and can't seem to get past this scenario:
Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of ...
6
votes
1answer
45 views
External Regret and Nash Equilibrium
There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.
The proof can be found in the survey ...
-1
votes
0answers
20 views
Information of a stream of bits [migrated]
Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream.
Let us call such stream as ...
0
votes
0answers
39 views
Parallelization of an iterative model
What I have:
An iterative process based on the application of a very simple algebra to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th ...
-2
votes
0answers
24 views
Normal form Lambda calculus expression [migrated]
I'm new here!
I need a little help with a lambda calculus reduction to normal form:
(λxxxx.xx)(λx.xx)(λx.x)y((λx.x)x)
It should be solved like this:
xx(λx.x)y((λx.x)x)
and then:
xx(λx.x)y(x)
...
3
votes
1answer
45 views
Zero Obstructed vertex induced subgraphs
Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:
It has no isolated vertices.
It is possible to ...
-2
votes
0answers
25 views
construct a TM from a PDA [migrated]
Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.
My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add ...
0
votes
0answers
59 views
Graph has several MST what does it mean combinatorically?
This question is not theoretical, it's about combinatorial meaning.
In graph theory there is a notion of complexity of a graph, which is equal to the number of spanning trees in a graph, which ...
6
votes
0answers
51 views
What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?
What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a ...
-4
votes
0answers
75 views
8 queen puzzle and 2057
In 8 queen puzzle, to reduce the search space, we use the incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc, avoiding the slots that are ...
3
votes
0answers
139 views
The number of maximal subsets with sum less than $m$
I've met this problem.
I would like to know to which complexity class it belongs.
Input
a set of positive integers $I$,
an integer $m$,
an integer $n$.
Question
Is the number of $S \subseteq I$ ...
0
votes
1answer
62 views
combinatorical embedding
I have a problem with the following statement :
Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G
What does this mean ?
OK in a spanning tree there ...
-1
votes
1answer
64 views
Various conjectures which is similar to Log Rank conjecture
Log rank conjecture is one of the most famous open problems in the area of communication compleixty.
Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , ...
0
votes
0answers
37 views
What's complexity of this “set linear programming” problem?
I came up with a problem below, which looks like a linear programming problem:
Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :
$$
\forall i=1, 2, 3,...,n\space\space \left | ...
5
votes
3answers
109 views
Decision problems vs functions
Complexity theory seems to be built around decision problems rather than functions. Who introduced this first and what is the reason for this choice? For example, Edmonds "Paths, trees and flowers" is ...
7
votes
4answers
218 views
Books/Lecture Notes on Parametrized Complexity
I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
1
vote
0answers
20 views
Grouping a set of rectangles in larger rectangular regions
I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me).
The approach I took was to consider central points of each rectangle as a ...
-4
votes
0answers
26 views
Need a simple example on time-stamp protocol?
I've seen the read & write conditions in time stamp protocol and got confused !
The applications using an example will make things clear.
thanks
-3
votes
0answers
65 views
Algorithm in NP for the k-coloring problem [migrated]
Does a generic algorithm exist that I could implement in an application to solve the $k$-coloring problem for any $k$ colors? I understand that such an algorithm would be $NP$, I'm just having trouble ...
1
vote
1answer
62 views
number of PCP queries
we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?
-6
votes
0answers
39 views
CalculatorVSCellPhone [closed]
"calculator or calculating machine, device for performing numerical computations; it may be mechanical, electromechanical, or electronic. The electronic computer is also a calculator but performs ...
4
votes
1answer
103 views
What is complexity of this max-edge subgraph problem?
While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:
Given a connected undirected graph, finding a ...
4
votes
3answers
119 views
Maximize quadratic function subject to linear constraints
Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?
This paper seems to come close to answering "no." They show it is ...
4
votes
0answers
47 views
+100
Looking for a refererence: equivalence of (semi)computable (semi)measures and PTMs
I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is ...
-4
votes
0answers
41 views
CoNp!=NP then P!=NP [migrated]
I am new here, and new in theory of complexity in general, this question is a part of a homework that I have got and I was stuck on it, does anyone has the answer? I need it to prepare for the exam.
...
3
votes
0answers
100 views
$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$? [migrated]
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.
My question is whether the converse is true: is ...
3
votes
0answers
63 views
Approximation factor when objective can be negative
In Williamson and Shmoys' textbook The Design of Approximation Algorithms they make the following assumption:
We assume that there is some objective function mapping each possible solution of an ...
11
votes
2answers
233 views
Checking if all products of a set of matrices eventually equal zero
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.
This means exactly what ...
2
votes
1answer
75 views
Lower Bound for the Parity Learning Problem
What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, ...
1
vote
1answer
42 views
bounds in centralized and distributed
If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?
1
vote
0answers
67 views
Quantum annealing vs adiabatic quantum computation
I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
13
votes
4answers
393 views
When does (or should) Theoretical CS care about intuitionistic proofs?
From what I understand (which is very little, so please correct me where I err!), theory of programming languages is often concerned with "intuitionistic" proofs. In my own interpretation, the ...
4
votes
3answers
101 views
Chomsky hierarchy for tree structures
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.
Is there a similar hierarchy for ...
-1
votes
0answers
42 views
Using software to calculate complexity of algorithm
I am somewhat a beginner, I have often seen complexity being calculated for various algorithms but they never actually gave me very clear idea about how it is done.
can someone please point some ...
3
votes
0answers
56 views
Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices
Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:
Their corresponding vertex induced subgraph has an even number of edges.
...
2
votes
0answers
56 views
Concentration Bounds for Dependent Rounding
Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:
At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
2
votes
1answer
50 views
Minimum shortest path cover of $n$ vertices in $R^m$
Informally, we define minimum shortest path cover to be the smallest number of shortest paths that cover all vertices of a graph. In other words, every vertex should belong to at least one of those ...
0
votes
0answers
34 views
Sparse inverse covariance estimation in high dimensional data
I am trying to estimate the sparse inverse covariance matrix in very high dimensional data, I mean with million variables. Up to now all the papers like this that I have found, they are limited to ...
0
votes
0answers
18 views
hyperspherical nature of K means (and other squared error clustering method)
This famous paper points out that any squared error based clustering method (K means being the most common example) tends to generate hyperspherical clusters. However, it does not point to a ...
4
votes
2answers
136 views
Approximation algorithm for finding the maximum common subgraph in two DAGs
Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a ...
0
votes
0answers
13 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. ...
3
votes
0answers
166 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
23 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
0answers
62 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts [migrated]
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 ...
3
votes
1answer
184 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
19 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 ...
7
votes
2answers
223 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 ...
