3
votes
0answers
14 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the ...
0
votes
0answers
13 views

Computing a sparse eigenvector

Given a matrix $A$ with distinct eigenvalues, can I find a sparsest eigenvector of it in polynomial time? It is tempting to say that one can simply compute the eigenvectors and pick the sparsest ...
0
votes
0answers
6 views

SLR(1) vs LALR(1) when we use SLR(1) Grammar

i'm so glad that ask my first question on my favorite site. Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for ...
-1
votes
0answers
30 views

Help me understand the worst case height for AVL trees [on hold]

I saw this equation about worst case height of AVL trees while studying, but I don't understand how we reach at the third line. $N(H) = 1 + N(H - 1) + N(H - 2)\\ N(H) > 2 * N(H-2)\\ N(H) \in ...
3
votes
1answer
69 views

MAX 1 in 2 SAT Algorithm

The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, ...
4
votes
2answers
80 views

Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
-4
votes
0answers
25 views

LEXICAL ANALYSIS [on hold]

Respected Sir, Which is the lexical analyzer used for compiling C programs.I think flex and lex are used to give us a view of how lexical analysis takes place.But I searched the internet but couldn't ...
7
votes
2answers
131 views

What are some good introductory books on type theory?

I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?
-1
votes
0answers
56 views

Cut-vertices between two given vertices in a DAG

Assume that we are given a directed acyclic graph. Given two vertices $v$ and $u$ we want to find all cut vertices between them. A vertex $x$ is a cut vertex we between $v$ and $u$ iff $u$ is ...
1
vote
0answers
59 views

Dynamic Programming with two optimization goals

I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I ...
1
vote
1answer
37 views

Finding a point outside of each of a set of polygons in a bounded space

I know there are algorithms for finding a point inside a simple polygon. Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm ...
-2
votes
1answer
57 views

Is this NP-Hard or does a known optimal polynomial time solution exist? [on hold]

Suppose we have 10 items, each of a different cost Items: {1,2,3,4,5,6,7,8,9,10} Cost: {2,5,1,1,5,1,1,3,4,10} and 3 customers {A,B,C}. Each customer has a requirement for a ...
-3
votes
0answers
32 views

LLAR(1) and SLR(1) tricky question [on hold]

Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE? ...
-3
votes
0answers
33 views

Is is decidable to check whether two PDA's accept same language or not? [on hold]

Whether two PDA's accept the same language or not. This problem is decidable or undecidable.?
-5
votes
0answers
29 views

If problem is np-complete then what are its subproblems, p or np? [on hold]

let A is an NP complete problem. and A is reduced to B, then what is B problem..? Is it np class problem or p class problem or both?
4
votes
0answers
44 views

Invert a number modulo a composite number

Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists, can we compute $a^{-1} \mod M$ in $O(\log^{b}(M))$ arithmetic computations where $b>0$ and is ...
0
votes
0answers
54 views

Highway dimension

I'm interested in understanding some recent theoretical results on pathfinding. Specifically this paper: http://research.microsoft.com/apps/pubs/default.aspx?id=201061 I understand from the paper ...
6
votes
2answers
133 views

Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for ...
3
votes
0answers
79 views

May Boolean circuits be exponentially more concise than Boolean formulae?

Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest ...
1
vote
1answer
49 views

Example of a $U^\omega$ that is not Deterministic Büchi recognizable

Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.
-1
votes
0answers
48 views

Communities in a graph

While studying about communities in a graph, i was curios regarding any algorithm which deals with projection of these communities in 2D/3D plane. Most of the algorithm i have studied were related to ...
-1
votes
1answer
42 views

finite automata under morphism

Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$ Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted ...
-5
votes
0answers
31 views

Shorter way to say the Foo whose name is Bar [on hold]

I often find myself writing sentences like the following Move the variable whose name is X to the class whose name is Y I wonder which is the correct way to write that sentence in a shorter ...
1
vote
0answers
74 views

exact cover set problem

i am searching an heuristic algorithm for a weighted exact cover problem shown here: http://en.wikipedia.org/wiki/Exact_cover On my research i only found algorithm which calculates all solutions ...
-9
votes
0answers
102 views

NP=P paper published in Springer March 2013 [on hold]

anyone knows about the following paper claiming that NP=P and published in Springer March 2013 ? "the International Conference on Advances in Engineering Technologies and Physical Science was held ...
-2
votes
2answers
63 views

recursive function t(n) = t(n-1) /( t(n-1)+1 ) [on hold]

Can anyone solve this recursive function? : t(n) = t(n-1) /( t(n-1)+1 )
-2
votes
0answers
72 views

Finding loop invariants for programs that exist entirely inside loops

Most books say the way to find a loop invariant is by weakening the post-condition of the loop, or by finding a generalization of the pre and post-conditions of the loop. But what about games and ...
-3
votes
0answers
53 views

Converting 3-SAT instances to Monotone NAE-3-SAT [on hold]

Can some one show me how to convert a concrete 3-SAT clause set to its corresponding Monotone-NAE-3-SAT form ? Thanks in Advance !
1
vote
1answer
131 views

Time complexity of d-dimensional convex hull

Consider the convex hull problem in $\Re^d$: Input: a list of $n$ points $S$ in $\Re^d$, Output: the vertices of the convex hull of $S$. What is the best lower bound on the time complexity of ...
-4
votes
0answers
38 views

Can anyone explain this intelligent computer flash card spacing algorithm? [on hold]

Apparently this is "off-topic" at the math section, so I'm trying here according to the help center. Algo is located at http://www.supermemo.com/english/algsm8.htm I(1)=OF[1,L+1] I(n)=I(n-1)*OF[n,AF] ...
1
vote
0answers
111 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
2
votes
0answers
94 views

Sieve Methods for Twin Primes - How to extract algorithm from formula

I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is ...
1
vote
0answers
74 views

How to define deep learning? [closed]

Ive read some articles about deep learning but I found its hard to provide a clear definition of deep learning. For me its like an intelligent feature selection method. But it seems that its not ...
3
votes
0answers
107 views

How powerful are weak complexity classes with powerful oracles?

I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true. ...
2
votes
0answers
57 views

Which paper to cite when referring to reservoir sampling *with replacement*?

As far as I can tell, the term "reservoir sampling" is commonly used to refer to sampling without replacement and references [1], [2], and [3] are cited while mentioning it. When referring to ...
-4
votes
0answers
37 views

Which programming language do you recommend to me while I'm going to study Artificial Intelligence? [closed]

I'm a bachelor student, by the way I'm going to major in Artificial Intelligence in higher educations. I used to use languages like Delphi, C#, PHP and a minimum of C/C++ before to develop windows ...
-2
votes
0answers
22 views

Clarification on ANN implementation

General Problem I need some clarification on the implementation of an Approximate Nearest Neighbor algorithm found here (7 pages, easy read). Algorithm Reproduced Here First there's a ...
-4
votes
0answers
29 views

Ways to remember Typed Lambda Calculus for Msc Exam [closed]

My friend is resitting his exam again next week for Postgradute Msc in Computer Science. The part he failed first time around was typed Lambda calculus formlae and applications. He knows how to do it, ...
-3
votes
0answers
41 views

Under which conditions the '+' operator is conservative, for regular expressions? [closed]

Which properties does a regular expression maintain after a string concatenation? Or under which conditions (either on the string or on the regexp) any property is maintained? Rewriting this in an ...
-1
votes
0answers
60 views

A question related to convex optimization

Suppose two non-negative convex functions $f$ and $g$ be given. We want to solve the following optimization $$\max_{g\leq\epsilon}f.$$ Now suppose that both $f$ and $g$ can be upper-bounded by a ...
36
votes
2answers
4k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
0
votes
0answers
102 views

Clustering in sublinear time/query

Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy: 1) Minimizing the number of balls that are required to cover all ...
15
votes
1answer
375 views

Edit distance in sublinear space

What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is ...
-4
votes
0answers
33 views

Bitwise Operations question [closed]

I'm new to computer science and recently took a class. I'm struggling with this question which i don't quiet understand though i'm aware of bitwise operations Can i have a clear explanation please ...
-2
votes
1answer
47 views

Practical topological sorting for dependency graphs

I have been reading the Wikipedia page on Topological Sorting, specifically the depth-first algorithm which also detects cycles while it is building the sort. But from some experimentation with this ...
5
votes
1answer
79 views

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
11
votes
1answer
466 views

To what extent can the mathematics of Reals be applied to Computable Reals?

Is there a general theorem that would state, with proper sanitization, that most known results regarding the use of real numbers can actually be used when considering only computable reals? Or is ...
8
votes
1answer
180 views

Fast algorithm for weighted bipartite matching problem

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks. I have an ...
4
votes
1answer
98 views

Does the 0-1 principle apply to merge networks?

For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list. What if I want to build a comparison-swap network for merging two pre-sorted ...
-1
votes
1answer
71 views

Consistency and completeness of any arbitrary 3-valued logic?

Based on the explanations here [1] I know that 3-valued first order logic has many different versions, which differ in the definition of their operations (e.g. implication). All of these (as far as I ...

15 30 50 per page