All Questions

10,208 questions
Filter by
Sorted by
Tagged with
82 views

Is equivalence of uniform AC0 decidable?

Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable? Since the languages defined by nondeterministic pushdown automata ...
327 views

A dynamic data structure to list triangles

Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations? Insert an edge into the graph Delete an edge from the graph Given a query ...
135 views

Is sorting pairwise distances as hard as sorting arbitrary points?

If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances? Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as ...
80 views

Switching lemma for polynomials over $\mathbb{F}_2$

Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$. Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total ...
84 views

Chain rule for KL divergence

Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the ...
64 views

reduction from SAT to approximate set cover

I read this neat result proved in the early 90s: For any $c>1$, There's a poly time map from boolean formulas $\varphi$ to pairs $K, \mathcal S$ where $K$ is a positive integer and $\mathcal S$ ...
170 views

58 views

132 views

Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
122 views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am ...
46 views

$\ell_\infty$ partially enclosing ball problem

Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? ...
43 views

Hard family for degree-$D$ MAX-3LIN

Max 3LIN is the problem where one is given a linear system of equations $C$ over $\mathbb{F}_2$ with $3$ variables per equation, and needs to determine the maximum number of equations that can be ...
26 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 ...
55 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....
68 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.
113 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 ...
84 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 ...
88 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 ...
199 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 ...
81 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 ...
376 views

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 + ...
67 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....
105 views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

I'm following course material from the course Advanced Data Structures. The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which ...
41 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 ...
70 views

176 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 ...
46 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$ ...
23 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 ...
101 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 ...
116 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?...
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 ...
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$. ...