All Questions

8
votes
1answer
156 views

P and Descriptive Complexity

In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. However, ...
1
vote
0answers
92 views

Parallel building time of a k-d tree on n points with n processors

Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree? A straight forward parallelization would be as ...
-1
votes
0answers
45 views

$k$th element in data stream

In the streaming model how can i find the $k$th element (not $k$th most frequent) with erorr of at most $\pm \epsilon$ s.t. we return index $i$ that $(1-\epsilon)k \leq i \leq (1+\epsilon)k$ using ...
6
votes
0answers
136 views

Can reciprocal inputs speed up monotone computations?

A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
2
votes
1answer
138 views

An equation relating Time complexity, Space complexity, and entropy of output

Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship ...
-2
votes
1answer
106 views

Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated. Note: P^NP means P with NP oracle
1
vote
0answers
21 views

whether two sets of stabilizer generators are related by a Clifford circuit

I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a ...
6
votes
1answer
157 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
8
votes
4answers
339 views

List of quantum-inspired algorithms

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra: A quantum-inspired classical ...
2
votes
0answers
70 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
3
votes
0answers
78 views

Is it possible to check equality of equi-recursive types, or recursive λ-terms?

Can we determine if two λ-terms are equal? Given two lambda terms, let's say they are equal if their (possibly infinite) Bohm trees are. Under this definition, for example, ...
2
votes
0answers
61 views

Complexity of counting Wang tiles

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
2
votes
0answers
49 views

How to improve this pseudorandom generator?

Let $f$ be a Boolean function and $\varepsilon > 0$. There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property. Let $T$ be a set and $...
2
votes
1answer
59 views

Weighted Min-Cut in bounded-genus graphs

What is the status of the following decision problem ? Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$ Output : ...
3
votes
0answers
56 views

Is #PP2DNF hard to approximate?

The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the ...
3
votes
1answer
105 views

Universe polymorphism: the inference of universes and their constraints

When making a universe polymorphic definition in Coq, universes and their constraints are automatically inferred. Are they somewhat the most general ones (in a sense similar to the principal type ...
2
votes
1answer
123 views

Would an NP-complete public key cryptosystem imply NP=co-NP?

Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of ...
0
votes
0answers
11 views

Is there a stochastic/online version of the GLM-Tron algorithm?

The GLM-Tron algorithm appeared in Theorem $1$ in this paper, https://arxiv.org/pdf/1104.2018.pdf Is there a stochastic version of this? (...essentially something that will randomly sample a few ...
5
votes
1answer
154 views

Is F<: with bottom undecidable?

We all know that F<: is undecidable: http://www.cse.chalmers.se/~abela/lehre/SS07/Typen/pierce93bounded.pdf However, I have difficulties finding that anyone claiming the version with bottom added ...
6
votes
1answer
169 views

Minimal generator for a set of sets

Is this a known problem? Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is ...
4
votes
0answers
127 views

Hereditary Substitution with Inductives and Eliminators?

I'm wondering, is there any existing work on hereditary substitution with inductive type families and dependent eliminators? In particular, normalizing the application of an eliminator to an ...
5
votes
2answers
104 views

Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf Valiant proves that there exists a $\...
3
votes
0answers
53 views

Conjugacy testing problem

The below-given problem is in black box setting means input is given by set of generators. Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $...
2
votes
0answers
78 views

What's the example of natural transformation in 'Type" that is not a parametric function?

Take a type theory of your choice (perhaps System Fω). Parametric functions are known to be natural transformations in 'Type' category. Yet not every natural transformation in 'Type' is a polymorphic ...
2
votes
1answer
77 views

Validity of a modal argument about “vagueness”

(2nd version to make explicit my implicit assumptions about A, B and C, and the definitions of the non-logical constants "⊂" and "≡".) Intuitively, the following modal argument seems valid to me and ...
6
votes
0answers
139 views

Bottleneck $k$-link path in a complete DAG

Let $G$ be a complete DAG: It has vertices $v_1,\ldots,v_n$, and $v_iv_j$ is an edge if and only if $i<j$. Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)&...
3
votes
1answer
91 views

Select circle with given radius that contains most points

Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points. I tried solving ...
2
votes
0answers
93 views

Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032 1) "A further problem that can be shown ...
2
votes
0answers
32 views

Minimize The Number of Connected Components in Hit-map of A Boolean Matrix

Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance): Is there any ...
6
votes
3answers
239 views

A partition problem in which some numbers may be cut

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard. However,...
6
votes
1answer
182 views

Where do people publish/submit their work on type theory?

Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published? Especially, I'm looking for more "pure mathematical" venues/journals which ...
1
vote
0answers
6 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
9
votes
1answer
156 views

Natural candidates for NP-E and E-NP

It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
0
votes
2answers
70 views

Bellman-Ford with Non-edge-decomposable Path Weights

Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a ...
4
votes
1answer
58 views

Solving an LP with at most m-1 nonzeros

Consider the linear program: $$ A x = b, ~~~~~~ x\geq 0 $$ where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$. It is known that, if this ...
6
votes
1answer
84 views

Is CoC inconsistent with cnat_ind axiom?

It is not possible to derive induction for Church-encoded datatypes on the Calculus of Constructions (source). Moreover, according to the accepted answer to another question, it is also not possible ...
6
votes
2answers
205 views

Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

There are many closed terms of a given type. For instance, both of these terms: $$ \lambda x . x $$ $$ \lambda x . (\lambda y . y) x $$ have a type of a polymorphic identity function: $$ \forall X ....
1
vote
0answers
55 views

What is the computational complexity of determining the mixing time of a Cayley graph?

Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles. Numberphile has a nice series of videos of Diaconis explaining the proof. I ...
5
votes
0answers
160 views

What's the fastest known algorithm for finding the diameter of a graph?

Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
5
votes
1answer
141 views

Viola's Reduction of 3XOR to listing triangles

Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles. Assume that given a graph in adjacency list format, with $m$ ...
2
votes
2answers
133 views

Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

S-T CONNECTEDNESS Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$ Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$. S-T CONNECTEDNESS problem is known to be #...
1
vote
0answers
14 views

Worst case polynomial in elimination theory under rank conditions?

Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
2
votes
1answer
91 views

Automata as term rewriting systems

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
6
votes
3answers
271 views

When a type is a value?

In functional programming and in the theoretical setting of the $\lambda$-calculus it is standard to consider a lambda abstraction $\lambda x.M$ as a value. In my understanding, the intuitive reason ...
2
votes
0answers
64 views

What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
13
votes
1answer
226 views

Is { ww' | HamDist(w,w')>1 } context-free?

After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove: Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|...
3
votes
1answer
144 views

Algebraic construction of $\varepsilon$-biased sets

Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by $$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$ It is then possible to ...
9
votes
3answers
363 views

Continuous mathematics and formal language theory

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...
8
votes
1answer
163 views

Reversible polynomial circuit iff polynomial reversible circuit?

My question is about efficiently computable bijective functions. Informally I'm interested in: If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...
5
votes
1answer
148 views

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...

15 30 50 per page