2
votes
2answers
10 views

Call-by-push-value's denotational semantics of “thunk diverge”

I was reading about Call-by-Push-Value in the introducing paper from 1999, but I have some confusion, partially because of my unfamiliarity with domain theory. I might have figured it out, but I'd ...
-2
votes
0answers
10 views

Reading suggestions

Is there any one who can give me some reading suggestions about information theory, machine learning and approximation theory? I found "Faster Algorithms via Approximation Theory(Sachdeva and ...
-3
votes
0answers
15 views

Grammar in Compiler Question

I know: A language is said to be LL(1) if it can be generated by a LL(1) grmmar. It can be shown that LL(1) grammars are not ambiguous and not left-recursive. ...
0
votes
0answers
34 views

Generalised Weighted Vertex Cover on Trees

Given a rooted vertex-weighted tree, find a minimum weighted vertex subset S such that every connected component on G-S has atmost k vertices. Is this problem already solved in polynomial time? ...
-1
votes
0answers
22 views

Name of the problem to find next lowest sum of elements

I'm looking for the name of the following problem: Given monotonically non-decreasing sequences A, B, C and function ...
-2
votes
0answers
31 views

Converting decision problems to grammars? [on hold]

I'm struggling to understand some concepts related to the relationship between language and computability theories. Can we convert decision problems to the corresponding grammars describing the ...
2
votes
1answer
60 views

Determining the number of clusters using property testing algorithm

We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of ...
1
vote
0answers
92 views

Graph sparsification

I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph ...
0
votes
0answers
96 views

Greater-Than operator using an Arithmetic Circuit

How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it? Where $x$ is the input to the ...
0
votes
0answers
31 views

linear combination of k sparse vector is 2k sparse proof [on hold]

I have been thinking about solving this problem and I am unable to get the lines of thought. What I have got so far is as follows: For the case of 2 dimensions, the points that lie on x or y axis ...
2
votes
1answer
57 views

Complexity class for quantum computer with commutative gates

BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be ...
1
vote
1answer
190 views

#P-complete problems are at least as hard as NP-complete problems

I just read J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983) and one of the first ...
-5
votes
0answers
21 views

doubt regarding power of graph [on hold]

could you help me in clarifying a doubt regarding how to find square of a graph g from graph g.the doubt occurs on 15th page of the document which I have shown you by the link given.the doubt is that ...
-5
votes
0answers
22 views

please explain in simple terms simrank [on hold]

please explain in simple terms the concept of simrank.I have to take a seminar on simrank but I couldn't get the mathematical equations that point to this topic.
1
vote
1answer
94 views

Separated 3Sum versus 3Sum problem

Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets? Let's define the problem "$k$-Sum" as follows: given a single finite set of integers ...
1
vote
1answer
78 views

What is necessary and/or sufficient requirement for a subring of a field to be computable?

As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring? Conditions on either field or subring are fine.
-2
votes
0answers
24 views

Is there an approximation formula for the series of reductions in a programming language?

Suppose we define a grammar which encodes a programming language - lets use the S K calculus for this example. One can easily enumerate the terms of that grammar. ...
3
votes
0answers
30 views

Non-objected oriented type theories that can express the $\nu Obj$ calculus

Odersky et al.'s $\nu Obj$ calculus [1] adds just enough dependent typeness on top of object oriented programming to express interfaces that define types (and consequently module systems and other ...
-3
votes
0answers
49 views

MSO logic for graph connectivity

Can connectivity of a graph be expressed in MSO logic so that Courcelle's Theorem can be applied?
0
votes
0answers
31 views

Is finding a solution of a satisfiability problem harder than deciding satisfiability? [migrated]

Is the act of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression? i.e. is there another way of finding ...
5
votes
0answers
55 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
0
votes
0answers
45 views

Can I represent a computer program on a Hilbert Curve?

I overheard in discussion tonight: You know - you can represent a computer program as points on a Hilbert Curve. Is there a reference that explains this concept? I can't seem to Google for it. ...
11
votes
1answer
184 views

Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
0
votes
0answers
18 views

Are there other names for multilayer perceptrons or multidimensional interpolants based on Kolmogorov's approximation work?

Are there other names for multilayer perceptrons that are used outside of the neural net community? At its core, multilayer perceptrons form a multidimensional interpolant of the form $$ ...
-2
votes
0answers
47 views

Existence of k-subset of n Integers with sum limited by S in time O(n) [on hold]

Given numbers $k$ and $S$ as well as a list of pairwise different integers $x_1, \ldots, x_n$. Does an index set $I \subseteq \{1,\ldots, n\}$ with $|I| = k$ and $\sum_{i\in I} x_i \leq S$ exist. One ...
4
votes
0answers
71 views

The exponential function over algebraic numbers

Given an algebraic number $\alpha$, I am interested in finding an approximation of $\Re(e^\alpha)$ up to a given precision, where $\Re()$ refers to the real part of the complex number. Formally, I ...
21
votes
3answers
508 views

How to find interesting research problems

Despite several years of classes, I'm still at a loss when it comes to choosing a research topic. I've been looking over papers from different areas and spoken with professors, and I'm beginning to ...
-1
votes
0answers
42 views

minimum weighted subgraph of a weighted complete graph

i have a complete weighted graph G with n vertices. i need to find an induced subgraph S of G with k vertices such that the weight should be global minimum
7
votes
1answer
208 views
+50

Finding similar vectors in subquadratic time

Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function. Examples of similarity function are cosine distance, $l_2$ norm, Hamming distance, Jaccard ...
9
votes
0answers
160 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
-2
votes
1answer
39 views

is +ve, Monotone 3SAT NP-complete? [closed]

Is the variant of 3SAT where we only have +ve literals still NP-complete ? (Remember that we can always substitute -ve literals with +ve ones and add adequate clauses) ... Appreciate an answer ...
5
votes
0answers
88 views

Extensions of Affine Dispersers

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
-2
votes
0answers
26 views

Learning resources for “Multi-agent systems” formal course [closed]

I am looking for learning resources about Multi-agent systems (i.e. the formal graduate or higher undergraduate university course). I am aware of some major books in the field like: "An ...
0
votes
0answers
57 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
2
votes
1answer
64 views

Approximating the value of k in $k$-mean clustering problem

Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
-4
votes
0answers
31 views

Self Servicing MAC(media Access control) Layer Host? [closed]

I have been trying hard to understand the self servicing mac layer host but couldn't derive any help until now .I have went through 2 research papers but they are simply not understable.... Can anyone ...
4
votes
1answer
106 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 ...
1
vote
0answers
99 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
68 views

SLR(1) vs LALR(1) when we use SLR(1) Grammar [closed]

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 ...
-2
votes
0answers
77 views

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

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) \backsim ...
7
votes
2answers
289 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
171 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?
11
votes
4answers
377 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
67 views

Cut-vertices between two given vertices in a DAG [closed]

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
125 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
47 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
76 views

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

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
2answers
148 views

Complexity of the inverse 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} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where ...
0
votes
0answers
72 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
172 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 ...

15 30 50 per page