0
votes
0answers
16 views

The meaning of separations in cryptography

From the paper of Impagliazzo and Rudich that separates black-box key agreement from one-way permutation: We provide strong evidence that it will be difficult to prove that secure secret agreement ...
-1
votes
0answers
17 views

Merge action of binomial heaps amortized time

The merge action of binomial heaps, I believe, has O(lg n) worst-case running time. http://en.wikipedia.org/wiki/Binomial_heap#Merge But I'm having some trouble applying amortized analysis. My ...
2
votes
0answers
22 views

What exactly are Moore machines?

Ok, don't be scared by the title - it is not that I don't know the concept of a Moore machine, or basic FSM concepts in general. However, I think that the term "Moore machine", despite being ...
0
votes
1answer
27 views

An algorithm for counting to Graham’s Number

I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory. I thougth of the way to organize counter suitable for ...
1
vote
0answers
53 views

Counting the number of K4

I was going over this paper and I don't understand a certain proof (section five phase 2). Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D ...
1
vote
1answer
89 views

What's known about basing one-way function on the $P \neq NP$ assumption?

Is there a conditional impossibility result or the question is completely open?
1
vote
0answers
68 views

Defintion of a Data Structure?

Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer ...
13
votes
0answers
145 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
-5
votes
0answers
27 views

Algorithm Convert into pseudo code [on hold]

I want to ask algorithm that how can we convert in pseudo code please help me?
1
vote
1answer
42 views

Set query in a universe with overlapping sets

Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$. And a collection of sets (no restriction on being disjoint or exhaustive etc.) which cover some items. Size of each set is bounded by ...
4
votes
0answers
74 views

What do we know about checking real-stability of multivariate complex polynomials?

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
2
votes
0answers
37 views

Concentration Bounds for Thompson sampling

This paper gives concentration results around the mean of the regret for variants of UCB algorithm in multi-armed stochastic bandits. However, I could not find any similar results for Thompson ...
-1
votes
0answers
52 views

Is there a lambda function that evaluates any other lambda function with any input expression?

When evaluating lambda expressions, I am a computing machine that evaluates a lambda function with an expression. Is there a lambda function that takes (I suppose) two arguments: a lambda function ...
1
vote
0answers
60 views

Multicuts composed of Min-Cuts

Multicuts or multiway cuts are (edge) cuts of minimum capacity that separate each pair of a set of terminals (a subset of the entire node set). For two terminals, this is the classical $s$-$t$ mincut ...
0
votes
0answers
29 views

Approximate distance preserving sparse graph representation that are not necessarily subgraphs

I am looking for a type of graph sparsifier that I think I have seen somewhere but now I can't find the paper anymore. I think the paper referred to it as a spanner, but that term is used for so many ...
4
votes
1answer
88 views
+50

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
3
votes
2answers
108 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
0
votes
1answer
62 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
0
votes
0answers
46 views

Average case complexity- Hardcore lemma

I wonder if the following lemma (Impagliazzo hardcore lemma) holds for other distributions rather than the uniform distribution: Let $f: \{0,1\}^n \to \{0,1\}$ be an $(S,\delta)-hard$ function with ...
-1
votes
0answers
28 views

Lower bound on treewidth of co-graph

What is lower bound on tree-width on the connected co-graph with $n$ vertices? The upper bound is $n - 1$, as clique is a co-graph.
0
votes
0answers
28 views

Characterization of an irreducible matrix

A matrix is irreducible, if it is not similar via some permutation to a block upper triangular matrix that has more than one block of positive size. Equivalently, for a 0-1 matrix, if it is viewed as ...
0
votes
1answer
54 views

Seeking for a game for modelling a problem using game thoery [on hold]

I have a problem which I want to formulate it as a game, using game theory. In this problem there is several agents, we can consider the agents as the employees of different offices, these agents have ...
2
votes
0answers
31 views

Hardness of Covering Arrays with $v=t=6$

A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the ...
7
votes
1answer
107 views

Communication problems for which a deterministic direct-sum theorem is not known to hold

It is an old open problem whether a direct-sum theorem holds for deterministic communication complexity, that is, whether solving $t$ independent instances of a problem is $t$ times harder than ...
3
votes
1answer
97 views

Paths and Probabilities for a Random Walk on a Graph

I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest ...
0
votes
0answers
50 views

Analysis of Parallel Algorithms

I've recently gone into the field of parallel algorithms, and I was wondering about one particular question. Is there such a thing as amortized analysis for parallel algorithms? For example, if I call ...
0
votes
1answer
86 views
+50

Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$. There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$. There are $462! \approx 1.419 × 10^{1032}$ possible ...
3
votes
0answers
43 views

Set cover approximation ratio as a function of m (number of sets)

Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an ...
-1
votes
0answers
32 views

The maximum of a submodular function which has no restrictions

The problem is to verify whether the maximum is greater than 0. It is mentioned in papers and various tutorials that the problem is NP-hard. For example, in footnotes of [1] and [2]. However, ...
2
votes
1answer
36 views

One sided approximation degree

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P_{i,\epsilon}$ be minimum multivariate polynomial such that $P_{i,\epsilon}=i\iff f=i$, $P_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff ...
10
votes
0answers
188 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
14
votes
2answers
612 views

What is known about this TSP variant?

This question was previously posted to Computer Science Stack Exchange here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
6
votes
2answers
243 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

DISCLAIMERI do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment. Suppose for a moment that $\mathbf{P} = ...
13
votes
1answer
244 views

$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the ...
1
vote
2answers
160 views

Shortest path in DAG with path dependent arc costs

I've got the following problem Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an ...
3
votes
1answer
91 views

Actual practical example of a prefix-free Turing-complete language

A theoretical construct that comes up a lot in algorithmic computability theory is a universal prefix-free language. For my purposes, this is a language with the following properties: its syntax is ...
-1
votes
0answers
41 views

why there is very few papers on Shamir 3-pass protocol?

why there is very few papers on Shamir 3-pass protocol ? I have compared between RSA and 3-pass control and I think 3 pass control is more secure. The problem of more calculations will diminish as ...
-2
votes
0answers
17 views

How to implement Multiple stacks in a single dimensional array? [closed]

Algorithm for Implementing Multiple Stacks in a single dimensional array.
-3
votes
0answers
48 views

Shortest Paths with Negative Cycles, capping negative sums to constant [closed]

I know that the Floyd-Warshall algorithm can calculate the shortest path between all pairs of vertices on a graph, provided there are no negative cycles (or find a negative cycle if one exists). ...
-4
votes
0answers
15 views

Binary Divison Question - Highlighted my confusion [closed]

I have highlighted in green the area of which I don't understand. Can someone please explain to me where the 000 comes from? thanks :-)
0
votes
0answers
76 views

Consequences of P = BPP for the relation of P and NP [closed]

The class $RP$ is defined as follows: $$x \in L \implies Pr[M(x) = 1] ≥ c > 0$$ $$x \notin L \implies Pr[M(x) = 0] = 1$$ While in the standard definition it is $c = \frac{2}{3}$, all definitions ...
0
votes
0answers
39 views

Enumerate all the possible paths in a directed acyclic graph: matrix multiplication or queue based solutions? [on hold]

I have the following problem: given a $G$, a source $s$ and a sink $t$ i have to enumerate all the possible paths between $s$ and $t$. Each node has an outdegree always $\leq 3$. Each path has an ...
-2
votes
0answers
19 views

How would a for loop differ in quantum computing? [closed]

Consider for example the following code: Array A = {a, b, c, d}; for ( int i = 0, i < A.length, i++){ if A[i]=="c" print["1"]; else print["0"] } and ...
5
votes
0answers
57 views

What is the space complexity of computing the eigenvectors of a matrix?

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
1
vote
0answers
48 views

Categorical way of factoring out points

Major rewrite justifiably asked for: I'm currently trying to get a categorical way of doing something called the Gelfond-Lifschitz reduct on a set of single-headed Horn clauses. The semantics is the ...
4
votes
1answer
166 views

Relativized world where $L^A=NP^A$

I wonder1 whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$. My first idea was to try $A:=SAT$, but then I thought ...
4
votes
1answer
104 views

Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can ...
0
votes
0answers
58 views

Understanding efficient classical simulation of quantum computing

I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate ...
1
vote
0answers
90 views

Has there been work on formal Semantics for linear algebra?

Could I get some references on formal semantics for a calculus on linear algebra that helps you study matrix or tensor based programming languages? I am looking for anything that encompasses linear or ...
-4
votes
0answers
39 views

What's wrong here, or, is CNF to DNF conversion in o(exp(n))? [migrated]

I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and ...

15 30 50 per page