# All Questions

10,094 questions
0answers
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 ...
0answers
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) ...
0answers
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....
0answers
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.
0answers
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 ...
0answers
94 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 ...
0answers
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 ...
0answers
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?
0answers
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 ...
2answers
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 ...
0answers
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 ...
0answers
156 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 + ...
0answers
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 ...
0answers
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....
0answers
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 ...
0answers
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 ...
0answers
69 views

0answers
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 ...
1answer
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 ...
0answers
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$ ...
0answers
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 ...
1answer
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 ...
0answers
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 ...
1answer
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?...
1answer
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 ...
1answer
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$. ...
0answers
105 views

### $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 ...
0answers
88 views

Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $... 1answer 81 views ### Lower bound on the worst-case unbiased coin flips to sample a distribution? Say that we have a distribution$\mathcal{D}$such that all probabitilities associated with it are$p$-bit fixed precision numbers, so: $$\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}... 0answers 36 views ### Extending the sequential calculus (logic over words) to allow a hierarchy of languages like the arithmetical hierarchy Let \Sigma be some finite alphabet. Then consider the logical language \mathcal L = \{ R_a : a \in \Sigma \} \cup \{ <,= \} and first order formulas. For a given first order formula \varphi a ... 1answer 43 views ### Min Cut with Vertices I have an undirected graph G with a set of vertices and edges. Each vertex has a weight w. Let's assume we have all vertices connected with some paths. I'm looking ... 0answers 42 views ### Can a bar code exist in a 3 dimensional pattern on a 2 dimensional format? I do not know if there is any information to be got from this picture, but to me it seams that the pattern could contain information? This is a 2D picture but the lines seem to appear to 3D. Are they ... 0answers 74 views ### How much computer science / software experience is needed for a math major to do work in AI? As a math major who is planning on getting their PhD in mathematics, how much computer science or software engineering experience/education do I need to comfortably do research in AI, i.e., would a ... 1answer 49 views ### QPIP minimal client quantum capabilities It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al: https://www.researchgate.net/publication/... 0answers 40 views ### Hardness of Approximation of Set Cover with Growing Size Bound I'm considering the minimum set cover problem with the constraint that each set contains at most k elements. Here, k depends on the size of the universe. For example, k may equal \log n,\sqrt ... 1answer 81 views ### Verified type checkers Most of the work on programming language metatheory mechanization focus on the declarative properties of the languages (e.g., type soundness), but fail to address the algorithmic side, i.e. the type ... 1answer 62 views ### Embedding a n-tree into a b-dimensional space Given a (directed) n-tree T=(N,E,r) rooted in r\in N, I want to represent each node n\in N at most as a m-dimensional vector v_n\in \mathbb{R}^m (From the current Yuri's reply, m cannot be ... 1answer 71 views ### Simple proof that splay trees have the dynamic finger property? Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ... 0answers 67 views ### Agnostic query learning of decision trees Gopalan, Kalai, Klivans gave an algorithm https://dl.acm.org/citation.cfm?id=1374376.1374451 for agnostically learning decision trees h:\{0,1\}^n\to\{0,1\} under the uniform distribution given ... 0answers 97 views ### Planar Exact Cover by even-size sets Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one. Is the following problem NP-complete? Planar Exact Cover by even-size sets Input: A set U, a ... 0answers 39 views ### Intersection of a recognizable language and a decidable language is decidable? [migrated] I'm having trouble with proving that "Intersection of a recognizable language anda decidable language is decidable. I assume this is true although I have no idea how to proof it. Can somebody point ... 0answers 64 views ### Complexity of a specific class of definite integrals INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is 0 or not can be NP-complete, as the following integral representation of the Number Partition ... 0answers 78 views ### A question about UE Much has been written about the class UP see related (even more in literature) example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played ... 1answer 87 views ### Difference between statically and dynamically typed languages When writing a course on computer science where students get an introduction to both Python and OCaml, I was on the verge of saying that Python is dynamically typed and OCaml is statically typed. I ... 0answers 30 views ### maximizing ratio of submodular and monotone function I am studying the problem of influence maximization and its variants. In this context I am trying to maximize$$\dfrac{\sigma(S)}{cost(S)}$$where the numerator is non-ve submodular monotone but the ... 0answers 25 views ### Software parallelization from an algebraic point of view I am a novice, self-learning1 programmer / computer scientist and I have been learning a little bit of abstract algebra and wondering of its applications to software design. To my knowledge, there ... 0answers 95 views ### Razborov-Smolensky polynomial argument on$\textrm{ACC}[q]$where$q$is a prime power It seems to be a folklore that we can "handle"$\textrm{ACC}[q]$circuits not only for prime$q$but prime power$q$. For example, authors of this paper say that ... any constant depth circuit ... 1answer 111 views ### Reductions in Descriptive Complexity Reducing one problem to another are well known in various settings, such as many-one, randomized, truth-table, logspace or a whole slew of other reductions. Descriptive complexity can alternately ... 0answers 51 views ### Graph automorphism with prescribed values Consider a graph$G$with vertices labeled$1,...,n$and edge weights$w_{ij}$. Recall an automorphism of G is a permutation$\sigma$of the vertex labels such that$w_{\sigma(i),\sigma(j)}=w_{ij}\$ ...

15 30 50 per page