0
votes
1answer
6 views

Formal semantics of tactics

Tactics are supposed to represent inference rules in a system, and it might seem unnecessary at first to formalize the semantics of tactics; nevertheless, modern theorem provers can have pretty ...
8
votes
3answers
178 views

Type-based memory safety without manual memory manage or runtime garbage collection?

Let's say we wanted a typeful, pure functional programming language, like Haskell or Idris, that is aimed at systems programming without garbage collection and has no runtime (or at least not more ...
2
votes
2answers
49 views

Equivalent formulation of complexity theory in Lambda Calculus?

In complexity theory the definition of time and space complexity both reference a universal Turing machine: resp. the number of steps before halting, and the number of cells on the tape touched. ...
13
votes
3answers
287 views

How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS ...
2
votes
0answers
29 views

What is the consequences of an upper bound for NP on PH?

I know that if NP = P, PH = P. What if we have an upper bound for NP which is not polynomial such as quasipolynomial? What would be upper bound for PH and why?
1
vote
1answer
27 views

Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
1
vote
0answers
22 views

Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
1
vote
0answers
57 views

Smallest disjoint union chain containing a sequence of sets

Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element. A family $\...
2
votes
0answers
31 views

Sample Complexity for Order Statistics

I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference. Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
8
votes
2answers
213 views

Min weight perfect matching with even number of red edges

Consider a weighted graph with some red edges. We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized. ...
8
votes
0answers
69 views

Shortest string in the intersection of regular languages

Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
-2
votes
0answers
22 views

Calling this Reeds-Shepp implementations

I am pretty new to coding and am working on a path planner that requires minimum reeds shepp curve length as input. For this I found an old piece of code written by S. Lavalle which can be found here: ...
3
votes
1answer
396 views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
0
votes
1answer
37 views

Polynomial approximation algorithm for set cover with assumption

We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover). We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal ...
2
votes
0answers
66 views

What is the complexity of this game?

This is a generalization of my previous question. Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
9
votes
1answer
1k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
-2
votes
0answers
52 views

Arithmetic progression of a language $L$ of $\sum^*$ [on hold]

Suppose the alphabet $\{0, 1\}$ of which I want to define the set of strings of $0's$ and $1's$ with no two consecutive $1's$ as follows: $L = \{\epsilon, 0, 1, 00, 11, 000, 001, 010, 100, 101, 0000, ...
3
votes
0answers
35 views

Counting/Enumerating Minimal Edge Covers

A Minimal Edge Cover $c$ is an Edge Cover such that no other Edge Cover is a proper subset of $c$. Questions Which is the complexity of counting Minimal Edge Covers? Do we know any non-...
1
vote
1answer
144 views

How can I rank paths through an HMM? [closed]

I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path ...
-1
votes
1answer
290 views

Duration Viterbi Algorithm

I am searching for some good resources to understand the Duration Viterbi algorithm. Does anyone knows a good resource to understand and learn how to model a Duration Viterbi Hidden Markov Chain ...
2
votes
0answers
44 views

Probabilistic linebreaking algorithm

I'm currently trying to implement this paper: Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th ...
13
votes
1answer
330 views

Problems in NC not known to lie in NC2

Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
1
vote
0answers
15 views

What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
10
votes
0answers
168 views

Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
2
votes
1answer
88 views

A coupon collector type problem with changing probabilities

Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\...
5
votes
1answer
94 views

Expander Graph from Hypergraph

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
6
votes
1answer
112 views

NP-Complete Static Square Puzzles

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
8
votes
1answer
127 views

What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda ...
11
votes
1answer
330 views

State of research on SHA-1 Collision Attacks

SHA-1 security has been discussed since an algorithm for finding collisions was first published at CRYPTO 2004 and has been subsequently improved. Wikipedia lists a couple of references, however it ...
-2
votes
0answers
40 views

Sorting a subset of a sorted set; does it need the merge sorting complexity?

Suppose that we have an algorithm in which we have a sorted list of objects like $L = (x_1, x_2, \ldots, x_n)$ (the indices denote the order of the objects). During the algorithm we have a loop where ...
-2
votes
0answers
47 views

Channel capacity as a limit on information storage

It is well-known that Shannon's channel capacity provides an upper bound on the amount of information (measured in bits/s) that can be reliably (i.e. with vanishing decoding error probability) ...
9
votes
0answers
99 views

Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution

It is well known that the pigeonhole principle $PHP_n^{n+1}$ is hard for general resolution. The original proof due to Haken is elegant. One first defines a complexity measure for derived clauses, in ...
-1
votes
0answers
64 views

Is this problem involving shortest paths NP hard?

A graph with positive edges is given along with several vehicles at specific vertices of the graph.One of the vehicles has a package that is required to be transferred to a destination node.The ...
-1
votes
0answers
36 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
11
votes
1answer
132 views

Linear circuit complexity classes

The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth. The $\textrm{NC}$-hierarchy is the union of those classes....
10
votes
1answer
248 views

Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$. If the sequence of Kolmogorov complexities $K(HALT_n)$ were $O(1)$, ...
2
votes
0answers
49 views

Linear optimization over intersection of totally unimodular matrices

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...
25
votes
11answers
813 views

Example where equivalence is easy but finding class representative is hard

Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent ...
12
votes
1answer
767 views

Number of 4 cycles

Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
3
votes
2answers
376 views

Is there a non-deterministic version of the complexity class PP?

From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?) Edit: Perhaps I ...
9
votes
1answer
195 views

Is algorithmic information theory still evolving?

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory. The field seems very interesting for me, but it seems everything is the field was done ...
5
votes
0answers
126 views

Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
1
vote
0answers
39 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
6
votes
0answers
99 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
8
votes
1answer
323 views

Proof techniques for showing that dependent type checking is decidable

I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
43
votes
5answers
5k views

What is the most intuitive dependent type theory I could learn?

I am interested in getting a really solid grasp on dependent typing. I've read most of TaPL and read (if not fully absorbed) 'Dependent Types' in ATTaPL. I've also read and skimmed a bunch of articles ...
7
votes
0answers
122 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
3
votes
1answer
151 views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP. Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper. Some Examples: 1. A paper by Shuichi ...
1
vote
1answer
267 views

Why semi-gradient is used instead of the true gradient in Q-learning?

In reinforcement learning, with function approximation, a popular cost function is the Mean value error. This involves a target value V_pi and a current value estimate V_hat. When deriving the update ...
-4
votes
0answers
27 views

The big question: does P=NP? [migrated]

I figured it was a shame that one of the biggest open questions in theoretical computer science was not listed here as a question. True, nobody has an answer (probably), but still. Some might argue ...

15 30 50 per page