1
vote
1answer
29 views

The concept of binary description by Ray Solomonoff

In this article, http://world.std.com/~rjs/rayfeb60.pdf in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$. My question - why are shorter strings ...
1
vote
0answers
26 views

The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least ...
1
vote
0answers
16 views

Expected length of longest construction path in Barabási–Albert Model

The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by ...
1
vote
0answers
34 views

Important papers in representation of Boolean functions

What are some of the important papers in the field of polynomial representation/approximation of Boolean functions? One such seem to be http://dl.acm.org/citation.cfm?id=129757
0
votes
0answers
29 views

How to prove the existence of a pure Nash equilibrium?

I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I ...
1
vote
0answers
32 views

What is the name of this data structure? (hash table with a limit on the number of entries)

Denote $[n] \triangleq \{1,2,\ldots,n\}$. Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, ...
6
votes
0answers
42 views

Algorithmic advantages of pathwidth over treewidth

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
2
votes
0answers
41 views

Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
1
vote
3answers
65 views

Finding outer face in plane graph (embedded planar graph)

I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices. Computing a ...
-3
votes
0answers
29 views

Every Problem in NP [migrated]

Is every NP problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
6
votes
0answers
29 views

What is the state of the art in cache algorithm theory?

I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a ...
3
votes
1answer
149 views

Is the problem NP-C or polynomially solvable?

I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the ...
1
vote
0answers
72 views

Fully Homomorphic Encryption over Integers

On the section 3 of the paper Fully Homomorphic Encryption over the Integers, there is a construction of a somewhat encryption scheme, as follow: key generation Choose an odd η-bit integer $p$ in ...
-4
votes
0answers
24 views

Proving optimality for a new algorithm that finds minimum spanning tree [on hold]

Below is an algorithm that finds the minimum spanning tree: ...
7
votes
0answers
105 views

Enumerating Planar Graphs of Bounded Treewidth

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...
1
vote
0answers
66 views

Properties of “second-order” NP (complete) languages

Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language: $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ ...
5
votes
0answers
41 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
3
votes
1answer
94 views

What is the first name of Bainbridge?

Bainbridge coauthored the paper `Functorial Polymorphism' with Freyd, Scedrov and Scott (DOI). What is his/her first name?
4
votes
1answer
136 views

Finding the minimum number of coordinates to change to get a vector inside a subspace

Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates ...
-1
votes
0answers
38 views

max_sat vs min_cut: theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
4
votes
2answers
123 views

Flat vs non-flat domains

My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer flat ...
5
votes
1answer
57 views

Commutativity of addition in polymorphic lambda calculus

In the article "Extensional models of polymorphism" by Breazu-Tannen and Coquand, natural numbers are presented using a Church-like encoding: $polyint = \forall t . (t \to t) \to t \to t$ Addition ...
5
votes
2answers
112 views

How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE). In other words, a ...
0
votes
0answers
27 views

Mapping load balancing to graph theory

I'm looking for algorithms that transform/reduce dynamic load balancing problem in a cluster to a flow problem. I have n machines each of them constantly performing a job, suppose a machine is ...
3
votes
0answers
55 views

Definition of Clique width of graph

The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations. I would like to know why the name clique width is given to this definition. ...
2
votes
1answer
125 views

Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm? ...
-4
votes
0answers
24 views

Puzzle + Deciding p / Np / Np-Hard / Np-Complete [on hold]

Ram and Shyam have been asked to show that a certain problem Π is NPcomplete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to ...
-1
votes
0answers
50 views

Show there exists a turing machine for the following language with these properties [on hold]

I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the ...
7
votes
1answer
158 views

What is the complexity of decision tree complexity?

Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity? (I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.) If ...
-1
votes
0answers
38 views

Turing machine's emptiness is undecidable How? [on hold]

So every Turing recognisable language has an enumerator. If i build a turing machine which uses the enumerator of language $L$ and accept it if it outputs anything and reject if it outputs nothing. ...
0
votes
0answers
50 views

Understanding MA protocol as a variant of TM for small space setting

MA protocol is one of the most basic models of interactive proofs. Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
-2
votes
0answers
13 views

cache memory mapping in computer organization [on hold]

I am having problem in cache memory question.. I am here with providing the solution of question no 4th and 5 th with the doubts i am having regarding it. 1... .... ...Memory location address ...
4
votes
1answer
76 views

Algorithm to find all intersections in set of simplices

What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)? In the ...
-1
votes
0answers
23 views

Etymology of “relational algebra” and “relational calculus” [duplicate]

Are relational algebra and relational calculus similar to "regular" algebra and calculus? Or why are they named like that?
-5
votes
0answers
26 views

Proof of regular languages [on hold]

Prove that the given language is not regular using the pumping lemma
-4
votes
0answers
47 views

Find a particular subset not empty of a graph

I have a problem that I don't know how to solve: Every edge of a general graph G = (VERTICES,EDGES) has a real number 0<=val<=1. Every node is indicated with a letter of the alphabet; G does ...
1
vote
0answers
64 views

Characterization of the Set of all s-t-Min-Cut Sets

I would like to know how to answer the following problem: Input: A family of sets $S$ over a universe $U$. Question: Is there a directed flow network $N$ with an edge labeling ...
-4
votes
0answers
42 views

Find subsets of nodes in a graph sum of all edges [on hold]

Is it possible to visit all the cycles in a graph not necessary directed, from the smaller to the bigger in a polynomial time alghoritm? Example of output: ABA = cycle of 2 nodes ABCA = cycle of 3 ...
2
votes
1answer
81 views

Applications of algebraic geometry in Boolean complexity

Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. ...
-2
votes
0answers
53 views

How to compare two matrices of size 3x3? [on hold]

I'm looking for how to compare two matrices of size 3x3 which are the input of the cellular neural network they are originally two images converted to a 3x3 matrices, Actually I want to know if the ...
0
votes
1answer
83 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
0
votes
0answers
56 views

k closest points that belong to a set

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind. I have a set of real vectors: $$ S = \lbrace v_1, \dots, v_n \rbrace $$ ...
-4
votes
0answers
28 views

CS Algorithms Connected-components [closed]

Prove by induction that two vertices are in the same connected compoment if and only if there are in the same set. 1) BaseCase: one vertex (WORKS) 2) Inductive hypothesis. Assume there is a path p ...
8
votes
2answers
151 views

Straight line complexity of monomials

Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$ we define $L(f)$ to be the straight-line complexity of $f$ over $k$. Let $F$ be the set of monomials of $f$, namely the ...
9
votes
2answers
189 views

How to judge the definition of computational complexity of reals is natural or suitable?

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
0
votes
0answers
32 views

0-1 min-cost flow with unit-capacity imposed on sets of nodes

I am now trying to solve a 0-1 min-cost flow with unit-capacity imposed on sets of nodes. Formally, the problem is given by \begin{equation} \begin{split} &\arg\min_{x} \sum_i c^s_i x^s_i + ...
-3
votes
0answers
41 views

Maximum flow problem with both minimum and maximum capacities [closed]

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
-6
votes
0answers
78 views

DESIGN A FUNCTION OF THE H FAMILY THAT SOLVES THE NP-COMPLETE SUM SUBSET PROBLEM IN O(n) [closed]

You could help me to review this work please, ... Any contribution is welcome. ...
3
votes
0answers
39 views

Bichromatic all nearest neighbors

Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where: $f(r) = \text{argmin}_{b \in B} |r - b|$ That is $f(r)$ is the closest point in $B$ to the point ...
-2
votes
0answers
139 views

How to reduce the computational complexity max algorithm in this specific case

We work over $\mathbb{R}_+^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that ...

15 30 50 per page