All Questions

-1
votes
0answers
24 views

Quantum Computer Function

I've been mildly researching quantum computers to figure out how entanglement and superposition are utilized for higher performance. I understand what these are and I've gotten to the point where it ...
2
votes
0answers
48 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
58 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 : ...
2
votes
0answers
52 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
93 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 ...
-1
votes
0answers
48 views

Complexity lower bound for problem in $2^k \cdot 2^{|A|}$ with monotonicity in $k$

My decision problem deals with synthesis from register automata: input: a register automaton $A$, a number $k$; return YES if there exists $k$-register transducer that realizes the automaton, else NO....
2
votes
1answer
116 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
89 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
150 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 ...
-1
votes
0answers
103 views

“Computational” Entropy, probability, and if I don't know A and B, I don't know A+B

I'm quite bad at information theory, but I'd like to understand it at some point, and more precisely the links it has with cryptography. I have a general idea/intuition of what is entropy, but usually ...
4
votes
0answers
120 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
101 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
52 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 $...
-1
votes
0answers
49 views

Reconstructing linear maps with particular properties using machine learning

Consider the expression $AX = Y$ with $A$ an $N\times N$ complex matrix, while $X,Y$ are $N$-dimensional complex vectors. Let's further assume that $A$ is unitary, $A^{\dagger}A= I$. $A$ also ...
2
votes
0answers
74 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
74 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
137 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)&...
2
votes
1answer
58 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
91 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
29 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
220 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
178 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 ...
9
votes
1answer
146 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}$...
-4
votes
0answers
25 views

Node-disjoint paths

Given a flow network and M the maximum number of node-disjoints paths from s to t, how can I implement an algorithm that computes those M paths ? I thought of iterating breadth first search to find ...
0
votes
2answers
69 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
0answers
94 views

Find algorithm for statiscits problem find all solutions if exist

please i am trying find algorithm for 3 months but unsuccesful, i asked my teaches of theretics informatics but unsuccesfull too. problem. for example my Mum give me 50€ with condition -> can spend ...
4
votes
1answer
56 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
80 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
189 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
53 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 ...
-1
votes
0answers
33 views

where extreme Daubechies wavelet coefficients would be useful?

Consider a function the following spaces: $$ \{f : \|(i\omega)k \hat f(\omega)\|_p ≤ 1, k ∈ N ∪ 0, p ∈ (1, ∞)\}. $$ Denote by $ \psi^m_D$ an orthonormal Daubechies wavelet of order m. One can find ...
5
votes
0answers
158 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
139 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$ ...
-1
votes
0answers
48 views

How could the No Free Lunch Theorem be applied to complexity classes

I was reading a chapter from a book, which states: (section 11.3.4) No Free Lunch (NFL) has not been proven to hold over the set of problems in the complexity class NP. I was confused because NP ...
2
votes
2answers
128 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
votes
0answers
13 views

Local decoding and PIR schemes

It is a simple fact that locally decodable codes yield private information retrieval schemes. However, isn't local decodability a "much" stronger notion (?) in the sense that in PIR schemes we do not ...
2
votes
1answer
86 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 ...
-1
votes
0answers
39 views

What is the difference between a Top type and a Unit type [migrated]

Wikipedia defines a Top type: (edited for readability) The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top However, the article goes on ...
6
votes
3answers
267 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
224 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
138 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
357 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 ...
6
votes
1answer
135 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 ...
3
votes
0answers
90 views

Is Circuit Minimization $P$-hard under logspace reductions?

By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string $x$ and a number $k$. Question: Does there exist a Boolean Circuit $C$...
-3
votes
2answers
159 views

Do Turing complete languages automatically have efficient algorithms [closed]

Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $\...
10
votes
3answers
300 views

Is the complement of { www | … } context-free?

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
6
votes
1answer
218 views

Size of complement of context-free language

Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$. What is known about $|\bar L_n|$? Note that it is known that $|L_n|$ is either ...

15 30 50 per page