All Questions

0
votes
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 ...
-3
votes
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) ...
0
votes
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....
0
votes
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.
1
vote
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 ...
-1
votes
0answers
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 ...
0
votes
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 ...
-3
votes
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?
2
votes
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 ...
3
votes
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 ...
2
votes
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 ...
9
votes
0answers
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 + ...
-2
votes
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 ...
2
votes
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....
-2
votes
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 ...
2
votes
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 ...
1
vote
0answers
69 views

How does Best Partition Communication Complexity behave under input transformations?

I'm looking for references about the behavior of communication complexity under input transformations. A specific toy example of the kind of question I'm interested in is the following. Let $f(x_1,......
2
votes
0answers
33 views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles. Question: Is there some constant $k$ so that the $...
-3
votes
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 ...
5
votes
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 ...
1
vote
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$ ...
1
vote
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 ...
2
votes
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 ...
-4
votes
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 ...
1
vote
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?...
5
votes
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 ...
2
votes
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$. ...
-6
votes
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 ...
4
votes
0answers
88 views

Expected vs actual amount of information leaked by an $l$-bits message

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 $...
2
votes
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}...
3
votes
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 ...
-1
votes
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 ...
-1
votes
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 ...
0
votes
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 ...
1
vote
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/...
3
votes
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 ...
2
votes
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 ...
1
vote
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 $...
7
votes
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 ...
1
vote
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 ...
4
votes
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 ...
-3
votes
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 ...
5
votes
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 ...
2
votes
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 ...
2
votes
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 ...
-2
votes
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 ...
-1
votes
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 ...
3
votes
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 ...
3
votes
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 ...
1
vote
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