0
votes
0answers
2 views

N input network sorting comparators

Prove that an n-input sorting network must contain at least one comparator between the ith and (i + 1)st lines for all i = 1, 2, . . . , n − 1. Can anyon help me to solve this problem ?! Thanks in ...
0
votes
0answers
52 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?
1
vote
0answers
26 views

Literature for representation for boolean functions

What is the standard literary reading to understand: $1)$ polynomial(including minimal) representation of boolean functions? $2)$ polynomial(including minimal) approximation of boolean functions? ...
0
votes
1answer
30 views

Can we design our own `if` clause in Normal Order evaluation

I have been reading SICP and have been thinking over a thing for quite some time related to evaluation using Substitution with ...
-1
votes
0answers
33 views

Best Hamiltonian Cycle Problem solver

What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market? Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances. I ...
2
votes
1answer
68 views

Gap in degree of representations of candidate boolean functions

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be one of the following Boolean function: $0)$ Equality function - $Eq_k^n(x)=1\iff x_1+\dots+x_n= k$ $1)$ Threshold function - ...
0
votes
1answer
26 views

Safety property as closed set [on hold]

In the paper "the existence of refinement mappings", the formal definition of safety property is defined as closed set which is based on the definition of closed set: $\sigma|_m$ denote the prefix of ...
0
votes
0answers
19 views

Is the bitonic sort algorithm stable?

I was wondering, is the bitonic sort algorithm stable? I searched the original paper, wikipedia and some tutorials, could not find it. It seems to me that it should be, as it is composed of merge / ...
-3
votes
0answers
43 views

how to create general star from spanning tree [on hold]

i had read a paper "Approximation algorithms for the shortest total path length spanning tree problem" .I am not getting what's a star and general star.can you explain with an example ...
-1
votes
0answers
52 views

Approximate Hard Problem

The Unique Game is easy to solve for exact solutions, but becomes extremely difficult for approximate solutions, with no exact solution available. It is quite against of our intuition. As it is known, ...
-2
votes
0answers
36 views

Determine if subgraph is spanning tree [on hold]

I am looking for algorithm that allow me to determine whether given subgraph is spanning tree or not.
-1
votes
0answers
16 views

Constructing a tree in a Fibonacci heap with a lower bound on height [on hold]

I am trying to make a tree of height Omega(n) in a Fibonacci heap of n elements. This other SE question and page 2 of this document both provide the same idea for an algorithm that would produce the ...
1
vote
0answers
26 views

NC algorithm for rank of skinny matrix

Suppose I want to find the rank of an $m \times n$ matrix $A$ over $GF(2)$, where $m \ll n$. The algorithms for rank in the literature seem to be focused on the case when $m = n$, giving a time ...
4
votes
2answers
170 views

Are there problems for which divide-and-conquer is provably useless?

When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the ...
3
votes
0answers
91 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue ...
1
vote
0answers
50 views

Candidate Boolean Function with efficient rational representation compared to polynomial representation

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be a boolean function. Let $d$ be the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents ...
-5
votes
0answers
33 views

Will subset construction always result in a DFA? [on hold]

I understand how converting an NFA to a DFA works, but I don't understand how we are GUARANTEED to get a DFA from subset (powerset) construction. For some reason, I think there is some NFA that ...
6
votes
0answers
39 views

Diameter of Cayley graphs of subgroups of $S_n$ without inverses

Babai and Seress proved that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length ...
-1
votes
0answers
20 views

Find all the Cycle Bases in a Undirected Graph

How to find all the Cycle Bases in a Undirected Graph For example, given the graph: 0 --- 1 | | \ | | \ 4 --- 3 - 2 the algorithm should return 1-2-3 ...
1
vote
1answer
54 views

Rational function for Parity function

Let $x_1,x_2,\dots x_n$ be literals. Let $P(x_1,x_2,\dots,x_n)$ be the parity function. What is the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents ...
-1
votes
0answers
39 views

Edge-based NP-hard problems for reduction

I have a problem formulation where the input is a undirected graph $G=(V,E)$, and the task is to add a set of new edges $F \subseteq V\times V \setminus E$ to $E$, but no node $v\in V$ receives more ...
0
votes
1answer
29 views

Reference request: Classical analog of quantum threshold theorem

For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space: ...
-1
votes
0answers
24 views

Is evolution by natural selection the most efficient form of self organization?

This question crosses a number of different categories, so I didn't know where to put it. Quite simply, if any system is able to undergo self-organization with initial inputs, and left to evole a near ...
4
votes
0answers
43 views

Efficient Reduction from Min Cut to st-Min Cut

I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut. But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
0
votes
0answers
25 views

What is the resolution of the apparent contradiction in the Practical Byzantine Fault Tolerance paper?

This question refers to the paper by Miguel Castro and Barbara Liskov. On Page 4, the fourth paragraph of 4.2, it says "the primary... multicasts a pre-prepare message with m piggybacked to all the ...
4
votes
1answer
31 views

How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem

Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for ...
8
votes
1answer
111 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
2
votes
1answer
77 views

Automata and a kind of pumping lemma on state transition function

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My ...
1
vote
0answers
35 views

Dynamic Multithreading Analysis of Cache Oblivious Matrix Multiplication

I am reading the paper of Frigo et. al., The Cache Complexity of Multithreaded Cache Oblivious Algorithms, 2007. They present an algorithm to multiply two $n \times n$ matrices. This algorithm is a ...
0
votes
1answer
110 views

NP-hardness of minimizing sum of weighted product

Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into ...
-6
votes
0answers
31 views

NP-hardness of n queens problem [on hold]

i have following questions 1> is this statemnt true or false: "If we could solve an NP-hard problem in polynomial time, this would prove P = NP." 2>is n queens problen np hard or just np??? 3> iam ...
-4
votes
0answers
31 views

Oracle reduction to 3SAT [on hold]

Show that there is an oracle A and a language L\in NP^A (NP TM with access to oracle A) such that L is not polynomial time reducible to 3SAT even when the machine computing the reduction is allowed ...
1
vote
1answer
53 views

Concurrent transactions satisfying “serializability” but not “snapshot isolation”

In [Lin et al@TODS'2009] (Page 5), a history of concurrent transactions satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$) is given as follows: $H_{example}: ...
7
votes
1answer
275 views

How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead. Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
0
votes
1answer
54 views

Converting a Hardware description language to a functional programming language

I am looking for some guidelines on converting a Hardware description language such as VHDL or Verilog to a Typed Language. The reason I want to do this is to formally verify a hardware whose ...
9
votes
2answers
175 views

What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject ...
1
vote
0answers
18 views

Extending Delaunay graphs in d-space

I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space. ...
-1
votes
1answer
88 views

Using master theorem when there is a constant in the recursive term [on hold]

Is it possible to use the master theorem to find the asymptotic growth of a function of the form: $$T(n) = aT(\frac{n}{b}+c)+f(n)$$ Where $c$ is a constant. Can we safely ignore this constant and use ...
0
votes
1answer
27 views

Flow networks: Push flow on either edges but not both!

I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)? I'm not sure if this is correct ...
6
votes
0answers
82 views

Representing boolean function by a rational function

What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?
2
votes
2answers
89 views

Graph-theoretic properties of the Wiener index

The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of its vertices. Are there useful graph-theoretic properties of this index?
1
vote
0answers
36 views

estimating the number of comparisons of Shell Sort

I would like to estimate the number of comparisons in ShellSort. I'm using $h_s = 2^s-1$, where $s=\left \lfloor{\log(n)}\right \rfloor, \left \lfloor{\log(n)}\right \rfloor -1, \dots, 1 $ ; I know ...
5
votes
1answer
122 views

Representing boolean function by a polynomial

Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are ...
-2
votes
0answers
48 views

shortest path algorithm cost calculation [on hold]

so the question goes like this: You are given a directed graph G=(V,E) and a weight function wt: E->R+. You are also given two distinguished nodes s,t ∈ V Write an algorithm that marks every node v ...
0
votes
0answers
187 views

What is the largest constant factor to ever appear in an algorithm? [closed]

What is the largest constant factor to ever appear in an algorithm and how much of a drawback it was for applying the algorithm in small and medium problem sizes? In other words, is there an algorithm ...
2
votes
1answer
60 views

Weighted furthest point voronoi diagrams

I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that. But I could not find anything on Weighted furthest point voronoi diagrams !! But ...
1
vote
0answers
65 views

What is the intuition behind simhash?

Why does simhash work? I understand how to implement the hash algorithm, mechanically, from the many articles such as http://matpalm.com/resemblance/simhash/. But is there a simple intuitive ...
12
votes
1answer
253 views

Optimal randomized comparison sorting

So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to ...
-4
votes
0answers
69 views

Time complexity VS physical time [closed]

I know that some of the theoretical CS guys do not like do discuss these subjects, but I think it's crucial to answer this question for this field to solve the "hard problems". "Time Complexity" ...
5
votes
0answers
106 views

The minimum entropy of a proper coloring of a graph

The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices ...

15 30 50 per page