# All Questions

10,094 questions
7 views

### Two question regarding coreset construictions

I have two questions regarding coreset construction of clustering problem In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for ...
22 views

### Approximation Algorithms, LP, Set Cover

Show that the integrality gap of the relaxation for for the following two variants of multiset multicover, based on LP (13.2), is not bounded by any function of n. Remove the restriction that M(S, e) ...
37 views

### Linear time algorithm for projective clustering

There is a lot of work in clustering of high dimensional data. In case of k-means, it is shown here that one can get an $(1+\epsilon)$-approximation in linear time, yielding a PTAS, by random sampling....
51 views

### What is sequence unification?

And why is it interesting? Please provide some examples. This text is here to circumvent the anti-spam filter which thinks my question is bad.
84 views

### Oracle separation between PH and PSPACE

I am having difficulty understanding the concept and intuition behind this proof. The proof deals with constructing an oracle $A$ relative to which $PH$ is separated from $PSPACE$. I have several ...
95 views

### Prove that 3SAT50 is NP-Complete [on hold]

The problem definition of 3SAT-N, meaning that: The problem is in 3-SAT clause form, but there are at least N possible combinations that render the target expression to true. How are you supposed to ...
70 views

### Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
25 views

### minimum cost spanning tree algorithm with benchmark graphs

I have developed one minimum cost spanning tree algorithm. How can I check the algorithm with benchmark graphs?
54 views

### Where in $PH$ are these problems?

Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)? If $G_1$ is ...
146 views

### How do continuations represent negations (under the Curry–Howard correspondence)?

Under the Curry–Howard correspondence, types can be thought of as propositions, and values inhabiting a type can be thought of as proofs that the corresponding proposition is true. (E.g., the ...
79 views

### Is $MSB$ of permanent and certifying half number of witnesses easy?

Can there be a $P$ algorithm to decide if number of perfect matchings is at least $(n!/2)+1$ for a bipartite graph on $n+n$ vertices? Can there be a $P$ algorithm to decide if number of witnesses ...
157 views
+50

### Deterministic error reduction, state-of-the-art?

Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are Independent runs + ...
54 views

### Closure of rational langages under morphisms

I have to prove that the set of rational or regular languages is closed by morphism on their alphabet. i.e. that the image of a rational language by a morphism is still rational. h being a morphism ...
57 views

### Looking for Research in Cryptographic Computing

I recall reading in college about a nascent research area regarding cryptographic techniques for secure computing, relating to zero-knowledge proofs, but I am having trouble remembering the exact term....
18 views

### Out of order arrival in LCFS scenario

with LCFS, which packet/process will be serviced first in case of out-of-order arrival: the recently arrived but stale, or the previously arrived but fresh packet? E.g. at $t = 5$, a comparatively ...
34 views

### AMQ (Bloom-filter like structure) lower bounds

I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the ...
69 views

34 views

### How to utilise when one able reduce 10000 bits input by 1 less 3/4 of times [closed]

If one is consistent able reduces input bitstring of eg 10000 bits into 1 bit less 3/4 of times consistent How would you go about implementing an algorithm to practical useful reduce eg a large input ...
146 views

### Correctness of AKS algorithm for shortest vector problem

Short question In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true? for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise ...
37 views

### relations between the degrees of a boolean function and its absolute function

Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
21 views

### Splay trees as dynamic weight-balanced trees?

Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows: The ...
92 views

### Why not include private randomness in internal communication information definition?

I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference. This isn't exactly a research question but I can't find a good place to ask it. Suppose ...
31 views

### turing machines [closed]

Create a first language,recognizable but not co-recognizable language, or and prove both properties of your language. To prove that a language (or its complement) is recognizable, you should give an ...
84 views

### Count satisfying assignments of CNF formulas over all possible negation assignments

Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?...
95 views

### k-testable languages with non-constant k?

Let $p_t(w)$ and $s_t(w)$ denote the prefix and suffix of length $t$ of the word $w$, respectively. If $|w| < t$, then $p_t(w) = s_t(w) = w$. Furthermore, let $i_t(w)$ be the set of infixes of ...
84 views

### Maximum Positive Negative Set Cover Problem

I am considering the following problem. Input: Given two disjoint subsets $A$ and $B$ and a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq A \cup B$ for all $i=1\ldots k$. ...
### $n^2 x n^2$ Sudoku Puzzles have equal amount of easy-instances that can be solved in $O(n^k)$ time, under experimentation so far this is correct
Introduction I found out that I can take any $n^2 x n^2$ puzzle, solve it and study its permutation pattern and implement it into a poly-time Sudoku Generator. I also found out that a limited subset ...