All Questions
9,928 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 ...