0
votes
0answers
2 views

How to translate the axiom schema of induction by Haskell-Curry?

I'm trying to understand the Haskell-Curry correspondence. I am comfortable with it for propositional logic, but get confused when $\forall, \exists$ quantifiers come in the picture. The axiom schema ...
-3
votes
0answers
9 views

Vanishing gradient in RNNs - yes or no?

One of the often cited issues in RNN training is the vanishing gradient problem (Y.Bengio et al. doi:10.1109/72.279181), (S.Hochreiter doi:10.1142/S0218488598000094), S.Hochreiter et al., (R.Pascanu ...
1
vote
0answers
14 views

Is generalized pigeonhole search known to be no harder than PPP?

Consider the TFNP search problem Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 ...
2
votes
0answers
52 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
-6
votes
0answers
25 views

What did Turing call Turing Machines?

I hope he didn't go with the uninspired "Turing Machines."
2
votes
0answers
30 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
3
votes
1answer
35 views

Is any QMA-intermediate problem known?

Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been ...
3
votes
0answers
63 views

Describing state machines mathematically

The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me. On the one hand, I am surprised to see that an important hardware protocol called "two-phase ...
-1
votes
1answer
88 views

Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $. I wonder the following ...
-2
votes
0answers
24 views

How to describe the exponential nature of adding complexity [on hold]

Is there a computer science term that describes adding complexity to an IT system? For example, adding an application to an organization isn't N+1 it's exponential in the possible interactions it ...
1
vote
1answer
53 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
0
votes
0answers
58 views

What is the number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My guess ...
0
votes
2answers
36 views

A continuous center point of a convex spherical polygon

In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point ...
3
votes
2answers
81 views

Primitive Recursive Definition : Binary numbers

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the ...
3
votes
1answer
48 views

Random flows through fixed network

A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the ...
1
vote
0answers
26 views

inapproximability of logarithic factor of indepence set

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
0
votes
1answer
53 views

What is a minimum vertex separator as in this definition?

In a research paper the following definition appears that I'm not able to understand completely. Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
2
votes
1answer
69 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
4
votes
0answers
57 views

Type theory for memory safe data structures

Data structures such as a doubly linked list and a B+ tree have blocks of memory that have multiple pointers to it. This creates the risk that a bug will allow memory to be accessed after being freed. ...
2
votes
0answers
58 views

Padding Arguments for Probabilistic Classes

Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or ...
-5
votes
1answer
49 views

an algorithm for halting problem that is recursively enumerable [on hold]

Halting problem is known to be undecidable and therefore no recursive algorithm for halting problem exists. However, I was wondering if recursively enumerable algorithm, that is Turing-recognizable ...
3
votes
2answers
61 views

What requirements should a denotational semantics for a programming language satisfy to be correct?

We have a programming language and its denotational semantic, like Tony Hoare's CSP with its syntax and denotational semantic e.g. stable failure and UTP. We want to extend the language (its ...
-1
votes
0answers
27 views

Finding the most part of common information

Let we have strings $x$ and $y$. I want to find the most part of extracting common information of $x$ and $y$, that is string $z$ with $C(z) + C(x|z) = C(x)$, $C(z) + C(y|z) = C(y)$, $C(z) \to max$ ...
0
votes
0answers
44 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
1
vote
0answers
102 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
8
votes
0answers
71 views

NEXPTIME-completeness with more time for reductions

One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
-1
votes
1answer
94 views

How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
4
votes
0answers
144 views

Hardness of UNAMBIGUOUS-3DM

Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution. Is there a ...
2
votes
1answer
66 views

Resource listing models with known VC dimension

Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it). ...
3
votes
1answer
131 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
0
votes
0answers
22 views

Video lectures on type systems [migrated]

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...
2
votes
0answers
33 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
9
votes
0answers
103 views

How to find the “hard” probability distribution on the input for recursive boolean functions?

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
1
vote
0answers
83 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
5
votes
0answers
120 views

DAG reachability with O(n log n) space and O(log n)-time queries?

For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm ...
5
votes
0answers
52 views

Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
0
votes
0answers
33 views

An efficient method to find the MLE of the combination of two point processes

[Cross-posted from http://mathoverflow.net/questions/176402/an-efficient-method-to-find-the-mle-of-the-combination-of-two-point-processes ] I have a point process defined in two parts as follows. ...
0
votes
1answer
43 views

References to learn more about graph laplacian.

I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which ...
2
votes
0answers
84 views

Generalizing Haskell: could we replace Hask with Cat?

N.B. I asked the same question on Stack Overflow but it was suggested that it is too theoretical for this forum. It is great that Haskell allows us to walk around in the category $Hask$. But ...
0
votes
0answers
22 views

Amortized analyzes [on hold]

If I have a function g(x) that I want to analyze its complexity using amortized analyzes using the potential method, and I get the following results: The function g(X) has 3 different states (for ...
3
votes
1answer
116 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
-1
votes
0answers
51 views

No 4-clique, but not 3-colorable? [closed]

I was asked an interesting question while studying for Algorithms exam: You know that a graph is not 3-colorable when there is a 4-clique. We can check if there is a 4-clique in polynomial time ...
5
votes
0answers
66 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S ...
-4
votes
0answers
26 views

Solving the following recursions using the Akra-Bazzi theorem [closed]

Can the following equations be solved using the Akra-Bazzi theorem and how? Also - I don't quite understand the h_i(x) part of the Akra-Bazzi theorem in Wikipedia. I'll appreciate an explanation. ...
4
votes
1answer
385 views

Is this behavior in a programming language inconsistent?

I'm developing a tiny programming language to try to wrap my head around type inference, and I'm trying to figure out if its behavior makes sense or not. Here's the problem: The identity function ...
0
votes
0answers
29 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
1
vote
0answers
52 views

About the position of side conditions in an inference rule

Sometimes I see people put side conditions above the inference line as if they were premises of an inference rule. This feels strange. My understanding (which may be wrong) is that a side condition ...
21
votes
1answer
307 views

The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
0
votes
1answer
169 views

Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
3
votes
0answers
64 views

minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...

15 30 50 per page