0
votes
0answers
51 views

When is counting coins NP-complete? [on hold]

having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete: All three (except the last one) ask how much goes to person ...
10
votes
0answers
70 views

Any polynomial which is hard to count but easy to decide?

Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial ...
1
vote
0answers
53 views

Reconstructing a string from random samples

What is known about the following problem? You're asked to reconstruct a string $S$ of known length $n$ over a known alphabet $\Sigma$ from a collection of uniformly and independently chosen $t$-long ...
3
votes
1answer
61 views

Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
0
votes
0answers
40 views

Connecting partial paths to form a hamiltonian cycle

For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect ...
4
votes
0answers
52 views

Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
4
votes
2answers
58 views

Applications of $p$-adic numbers in CS

Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?
10
votes
1answer
118 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
-1
votes
0answers
59 views

Is the SAT variant where exactly k variables must be set to true known?

Consider the following satisfiability variant: Given a CNF formula $F$ and an integer $k$, decide if there is an assignment $\phi$ such that $F$ is satisfied under $\phi$, and $\phi$ sets exactly ...
3
votes
2answers
53 views

Lower bound proof for compressive sensing (Gel'fand widths)?

Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered ...
-1
votes
0answers
37 views

Support tortoise svn application [on hold]

Am currently working on developing an desktop application we could use at our startup to function along side the current repository tortoise svn and also monitor and track developer activity ( ...
7
votes
3answers
209 views

Are EXPSPACE-complete problems rare?

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up. So far, I found these, and I have ...
2
votes
1answer
26 views

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
1
vote
0answers
34 views

Testing - Correcting Pairs in PCPs

The BLR linearity test and the low degree test are two common tools in PCPs. By my understanding these tests ensure bounds such that (self-) correctors can be applied. I have two questions regarding ...
1
vote
0answers
20 views

Minimizing a general submodular pseudo boolean function

Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?
22
votes
13answers
6k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
-3
votes
0answers
29 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated. Are they both in use now a days ? ...
-1
votes
0answers
68 views

Necessity of a Turing machine for a given problem in order to reduce it to another [on hold]

I found it surprising that a certain type of reduction hasn't been flagged anywhere (except in Cook's original 1971 proof). Yes, there are Cook reductions (also known as Turing reduction), and the ...
7
votes
1answer
87 views

Randomized identity-testing for high degree polynomials?

Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time ...
-2
votes
0answers
34 views

Aggregated Analysis [on hold]

The answer is .................................. I am trying to study the answer but I have couple of confusions. how did they come with (n-1/2) / (1-1/2) in the 3rd line of the answer. What ...
-1
votes
0answers
33 views

How prevalent are traffic control algorithms?

Can anyone point me to some algorithms that specialize in traffic control and prevention? I am always wondering if traffic lights optimize for specific conditions.
2
votes
1answer
224 views

Complexity lower bound of finding the factorial of a number

I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read. Two similar problems, Matrix Multiplication and ...
-2
votes
0answers
53 views

need help with java, please anwser :) I have been using bluej [on hold]

Implement a Book class for a book store as described: A Book has a title, cost, and number in stock. Set the title and cost to values passed to the constructor. Create a “get method” for each ...
0
votes
0answers
84 views

Simple explanation of the O(n log n) algorithm for matrix chain multiplication

I've seen references to papers that talk of an algorithm that is able to compute the optimal order for multiplying matrices to reduce the number of operations (matrix chain multiplication), but does ...
-3
votes
0answers
26 views

three address code for matrix multiplication

Can somebody please give me the 3 address code for the following matrix multiplication: for (i=1 to n) do for (j=1 to n) do c[i,j]=0; for(i=1 to n) do for(j=1 to n) do for (k=1 to n) do ...
-3
votes
0answers
20 views

N input network sorting comparators [on hold]

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 ...
2
votes
1answer
168 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?
2
votes
0answers
55 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
44 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 ...
0
votes
0answers
55 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 ...
3
votes
1answer
85 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
33 views

Safety property as closed set [closed]

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 ...
1
vote
0answers
43 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
48 views

how to create general star from spanning tree [closed]

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 ...
0
votes
0answers
86 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
41 views

Determine if subgraph is spanning tree [closed]

I am looking for algorithm that allow me to determine whether given subgraph is spanning tree or not.
1
vote
0answers
29 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 ...
7
votes
2answers
372 views

Are there problems for which divide-and-conquer / recursion 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
108 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
57 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
35 views

Will subset construction always result in a DFA? [closed]

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
45 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
24 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
61 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
42 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
34 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
29 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 ...
5
votes
0answers
60 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
34 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 ...

15 30 50 per page