# All Questions

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 ...
10 views

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 ...
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. ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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.
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. ...
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 ...
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?
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 ...
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 ...
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. ...
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 ...
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  ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
77 views