All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
70 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
Boran Erol's user avatar
3 votes
1 answer
80 views

What are some practical applications of inductive-inductive and inductive-recursive types?

Since this question got not many answers Im hoping asking again could convey that this has some importance. Anyway so in undergraduate education, I was working on research to implement dependent-...
AnonymousThunk's user avatar
3 votes
1 answer
115 views

How well can shortest common supersequence over small alphabet size be approximated?

Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
Hao S's user avatar
  • 228
0 votes
1 answer
83 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
user1868607's user avatar
  • 1,049
2 votes
0 answers
105 views

Constructing complex languages without "recursion"

I'm curious of the ways we can construct provably complex languages. In particular, most constructions (i.e., the one used for proving the Time hierarchy theorem) seem to rely on encodings of Turing ...
mti's user avatar
  • 117
3 votes
0 answers
83 views

Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
Alexey Slizkov's user avatar
0 votes
0 answers
104 views

By Gödel numbering, is the set of computable(partially) transcendental numbers an immune set, productive set? [duplicate]

Every Turing Machine computing(output) real number is encoded as a natural number, namely, admissible numbering. Then what is the set of computable (partially) transcendental numbers? Is it an immune ...
XL _At_Here_There's user avatar
0 votes
0 answers
53 views

Shortest sequence that contains a given list of sequences as subsequences

Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences? Very similar to the question ...
Hao S's user avatar
  • 228
-1 votes
1 answer
54 views

Computability/Complexity of optimization problems in general

Dear StackExchange community, I have a question, or better phrased I am confused and would like to be enlightened by you! So assume we have a (optimization) problem like that: Instance: Let $f:\...
Thinklex's user avatar
1 vote
1 answer
64 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
user1868607's user avatar
  • 1,049
0 votes
2 answers
92 views

strong NP-completeness of multi-dimensional Equal-Subset-Sum

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty ...
caduk's user avatar
  • 101
8 votes
1 answer
248 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

The question: Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM? I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} ...
Neal Young's user avatar
  • 10.8k
0 votes
0 answers
46 views

Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
happyfeet's user avatar
1 vote
0 answers
63 views

Not possible to write deterministic CFG for balanced parenthesis?

I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language. But what's an example of ...
Jerry Ding's user avatar
5 votes
2 answers
151 views

Modify DCFG to enforce length limit

Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
Jerry Ding's user avatar
1 vote
0 answers
36 views

Unclear relation in the number of permutations consistent with Hasse diagrams

I have been reading the paper 'Time Space Tradeoff for Sorting on Non-Oblivious Machines' by Borodin et al. (Link). Lemma 1 in that paper gives a relation between the number of permutations consistent ...
Tharrmashastha V's user avatar
6 votes
0 answers
120 views

How to prove clock equivalence is a time-abstracted bisimulation

An important step of developing the theory of timed automata is to reduce the question of reachability in the timed automata, which has infinitely-many states, to the question of reachability in an ...
generic_logician's user avatar
0 votes
0 answers
25 views

Is it accurate to describe a computer as a dynamic memory state?

is this an accurate statement? And where can I find out more about these topics? At any point in time a computer is holding a memory state. Because the computer is moving in various ways we can call ...
SuperCat's user avatar
4 votes
0 answers
156 views

Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
Manish Kumar's user avatar
-1 votes
1 answer
129 views

What theorems are interesting in a monad?

In a monad, one can prove that the Kleisli composition is associative, and eta is its right and left unit, this is the famous monoid in the endofunctor category: ...
Gergely's user avatar
  • 123
0 votes
0 answers
34 views

Is there an interpretation of efficiency in learning theory in terms of where the probability mass is concentrated?

Let $\mathcal{X}$ denotes the input space of dimension $n$, $\mathcal{Y}$ denotes the codomain. In PAC learning with realizability assumption, we assume randomness over covariates $\mathcal{D}_{\...
ayaxxx's user avatar
  • 120
1 vote
1 answer
178 views

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and ...
Oscar Bender-Stone's user avatar
0 votes
0 answers
117 views

Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
Hao S's user avatar
  • 228
1 vote
0 answers
54 views

Is there a sharp phase change on error rate near the error correction threshold?

My rough intuition is that if we want to efficiently compute using noisy gates, the probability of success will exhibit threshold behavior as we cross the error correction threshold. Here is an ...
Geoffrey Irving's user avatar
13 votes
4 answers
1k views

List of nice non-context-free languages

I am trying to separate classes of formal languages from each other. One of these classes is the class of context-free languages. To this end, it would be handy to have a list of languages which are ...
NerdOnTour's user avatar
0 votes
0 answers
60 views

What is Shutt abstractiveness?

In software development, there is a pre-formal notion of abstraction. Several attempts have been made to formalize it. In particular, what is Shutt abstraction, or Shutt abstractiveness, and how does ...
Corbin's user avatar
  • 271
3 votes
0 answers
75 views

What is the actual difference between uniformity conditions for NC¹

I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for $k\geq 2$ $NC^k$ the uniformity conditions are equivalent, but for NC¹ they are not. I am ...
lzrdnb's user avatar
  • 31
3 votes
1 answer
133 views

Is there a full abstraction result for an untyped lambda calculus?

Famously, the denotational semantics of PCF in Scott domains is not fully abstract. But by adding the parallel or construct to PCF, a fully abstract semantics can be obtained. Is there an analogous ...
Nick Rioux's user avatar
2 votes
1 answer
394 views

A question on combinatorial algorithm

Given n sets $S_1,...,S_n$ such that $S_i \subset \{1,...,n\}$ is there a poly(n) algorithm to find $1 \leq i_1 < i_2 <.... < i_k \leq n$ such that $|\bigcup_{j=1}^k S_{i_j} | = k$ where $1 \...
Rishabh Kothary's user avatar
1 vote
0 answers
41 views

Convergence rates for the iterates of SGD on Lipschitz convex functions

Let $f:X \rightarrow \mathbb{R}$ be a convex and $L$-Lipschitz continuous function. Suppose $f^* = \min_{x \in X} f(x) \in \mathbb{R}$ and let $X^* = \{x \in X : f(x) = f^*\}$. For a non-negative ...
Andrea's user avatar
  • 319
6 votes
1 answer
192 views

What online talks should everyone watch? [duplicate]

In the past 4-5 years or so, partly owing to COVID, more and more talks have been uploaded to YouTube. In the same spirit as this question by Ryan Williams almost 14 years ago: What papers should ...
Tejas's user avatar
  • 369
1 vote
0 answers
85 views

What would be the cost to factor a 1024‒bits RSA modulus most economically within months today?

Of course this is a question with an answer that is due to evolve. A 2002 paper about TWIRL stated that the cost would be around 10M$$ and an other 10M$ to manufacture the devices. A later 2007 paper ...
user2284570's user avatar
1 vote
0 answers
44 views

Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
-3 votes
1 answer
155 views

The most complex language? [closed]

I'm interested in understanding the complexity of languages. If I wanted to construct a language that is very difficult to decide, how would I go about this? Is it known whether we can artificially ...
mti's user avatar
  • 117
11 votes
11 answers
5k views

Data structure whose name starts with the letter “N”?

I’m working on an “ABC” poster of data structures, with one data structure per letter of the alphabet. (It’s intended as decor for a child’s room.) I teach an advanced data structures course and it ...
7 votes
0 answers
101 views

Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
user11718766's user avatar
1 vote
0 answers
104 views

Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
Demi's user avatar
  • 528
0 votes
0 answers
21 views

Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
88 views

Abstract domain monad

I was reading old lecture from a CS course at Cornel and I have some doubts about the following at 2.4 It defines how to transform domains between each other via a Galois Insertion, more formally: ...
Alecs's user avatar
  • 11
8 votes
0 answers
281 views

Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
domotorp's user avatar
  • 14k
0 votes
0 answers
57 views

How to estimate slope of a feature in image?

I am working on analyzing data obtained from acoustic sensors. During analysis of acoustic data, I got frequency-wavenumber spectrum of acoustic data as shown below. I am looking for a technique that ...
Petroleum Engineer's user avatar
4 votes
0 answers
60 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
orlp's user avatar
  • 885
0 votes
1 answer
56 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
BBK's user avatar
  • 103
1 vote
1 answer
65 views

Sequential Two-player Game related to "Bandit Detection"

Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x_t$ which is represented by a ...
Amaryllis 's user avatar
-1 votes
1 answer
87 views

The role of Turing machines in computational complexity [closed]

In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
Sanyo Mn's user avatar
2 votes
0 answers
68 views

Distance between Fourier distributions of independent random Boolean functions

For a boolean function $f: \{-1,+1\}^n \to \{-1,+1\}$, the squared Fourier coefficients $\{\hat{f}(S)^2\}_{S \subseteq \{0,1\}^n}$ form a probability distribution. I want to know what the total ...
helloworld's user avatar
2 votes
0 answers
182 views

Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?

There are $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$ possible $n$-element subsets of a $2n$-element set. Therefore, any data structure storing such a set must use at least $2n - O(\...
templatetypedef's user avatar
2 votes
1 answer
208 views

Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
FooFighter39's user avatar
2 votes
0 answers
76 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
110 views

Monads whose Kleisli arrows can be "applicativized"

Has anyone thought about what constraints a monad should satisfy in order for its arrows to be able to be "applicativized". That is, for what monads $M$ is it the case that there is an ...
Julian G.'s user avatar

15 30 50 per page