# All Questions

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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
36 views

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

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

Algorithm for Implementing Multiple Stacks in a single dimensional array.
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). ...
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 :-)
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...