All Questions

Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...

The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows: $$A_1 = \begin{...

We proved in a section class the undecidability of the inclusion problem for $\mathsf{CFGs}$––that is, given two $\mathsf{CFGs}$ $G_1$ and $G_2$, is $L(G_1) \subseteq L(G_2)$––by proving that the ...

Suppose I want to find the minimum weight cut in a weighted undirected graph. I see Stoer–Wagner algorithm mincut algorithm does help to find the minimum cut. Is there an algorithm similar to Stoer–...

We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...

Are there classes of $SAT$ problems cast as integer programming solvable by parametrized strongly polynomial time simplex algorithm versions such as https://www.tandfonline.com/doi/full/10.1080/...

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

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

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

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

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

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$ ...

I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \...

The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries. I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to ...

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...

Let $f\in (\mathbb{Z}/p\mathbb{Z})^\ast$ be a nonzero element of a prime finite field. For $d, r\in \mathbb{N}$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a_0 +...

In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem. Given an image with black background that contains blobs whose ...

As discussed in the answer for this question, it is not necessary that two k-regular graphs are always isomorphic to each other. However, 2-regular graphs are isomorphic. So my question is if there ...

I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ...

I've just started taking a serious interest in reading ground material lately, and I'm probably asking this question at the wrong time. So let me know and I'll delete it. I just can't for this ...

My graph is as follows: I need to find a maximum weight subgraph. The problem is as follows: There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...

I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to ...

Suppose $f:\{0,1\}^n \to \{0,1\}$ is a function such that it can be computed by a circuit of size $n^c$ for some constant $c>0$. Q. Is there any nontrivial upper bound on the depth of a circuit ...

I have a set of $m$ sets, each one has $n$ different items. I have a function $f: 2^n \to \mathbb{R}$. ($f$ could be submodular if it helps). I am trying to maximize the function $f$ under the ...

We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers ...

I have a question about the paper "Planar graph coloring is not self-reducible" by Samir Khuller and Vijay Vazirani. The final theorem in that paper states that "Planar Graph k-coloring is not self ...

I wonder what is known about the two following maximisation problems. Maximum weight connected subgraph : Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$ Output :...

If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...

Suppose we have some list of rational numbers where the order in which the numbers are listed is arbitrary. What is the representation of this list which is most compact (i.e. "smallest amount of ...

Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...

What are some examples of theorems of the form "If $X$, then $PH$ collapses", but where the proof does not say which level $PH$ collapses to? The canonical example would be "If $PH = PSPACE$, then $...

I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections. Given $n$ inputs numbered $1 ......

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...

In Jain et. al (2003), at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega(\frac{\...

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

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

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

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

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

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

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.

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

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

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

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

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

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 + ...

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

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