All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 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
158 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
130 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
35 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
  • 122
1 vote
1 answer
182 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
118 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
55 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
62 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
76 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
139 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
411 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
42 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
193 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
89 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
45 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
157 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
108 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
107 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
22 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
89 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
302 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
  • 14.1k
0 votes
0 answers
58 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
62 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
58 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
68 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
89 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
69 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
183 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
227 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
78 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
113 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
0 votes
0 answers
71 views

Is every 4-claw-free graph a bounded degree graph?

I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3. As per my observations, this type of independent set size ...
user72110's user avatar
0 votes
0 answers
39 views

converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
TheoryQuest1's user avatar
2 votes
1 answer
127 views

Enumerating all Vertex Covers of Size at most $k$

I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most $k$? Is there any algorithm that can achieve ...
Sugyani's user avatar
  • 23
5 votes
2 answers
502 views

What is the relevance of Real Analysis in TCS?

I'm a recent Math major who switched to a double major with Computer Science. I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data ...
wonderinghuh's user avatar
4 votes
0 answers
83 views

Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
Mingda Qiao's user avatar
1 vote
0 answers
42 views

Placing a circle in a point cloud

I need to place a circle with fixed radius in a cloud of points. The circle also must lay in a polygon (the points are also in that polygon) This circle has to contain as many points as possible. Are ...
fanda's user avatar
  • 11
12 votes
2 answers
707 views

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
Prafullkumar Tale's user avatar
4 votes
0 answers
52 views

Complexity of solving random underdetermined polynomial equations over finite fields

Consider a random system of degree-$d$ polynomials, with $n$ variables and $m$ equations, over some finite field $\mathbb{F}_q:$ $$\begin{align}\sum_{\substack{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}...
Quang Dao's user avatar
3 votes
0 answers
79 views

Hardness of Approximation for Three Matroid Intersection

I am searching for the best known hardness of approximation bound for three matroid intersection. The input is three matroids on the same ground set which are accessible using three different ...
MatroMan's user avatar
0 votes
0 answers
97 views

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
Manish Kumar's user avatar
3 votes
0 answers
45 views

Affine point matching in general dimensions

Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
rr314's user avatar
  • 131
2 votes
0 answers
43 views

Characterization of CF languages closed under circular shifts

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts? Are there simple characterizations/properties of Context Free ...
Marzio De Biasi's user avatar
0 votes
2 answers
220 views

Shortest path with permutations and fixed dimension

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
user1868607's user avatar
  • 1,049
1 vote
0 answers
71 views

Is there a succinct representation of factoring which remains computationally intractable?

I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
Hans Schmuber's user avatar
1 vote
2 answers
401 views

Nondeterministic Turing Machines as deciders, versus NP and co-NP

While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step. Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
Arnaud Casteigts's user avatar
0 votes
0 answers
97 views

What algorithms are there for ANN?

I'm a software engineer working on a large project for which one of the subcomponents involves approximately solving the nearest neighbors problem (to a factor of $1+\epsilon$). I was wondering what ...
Jaclyn's user avatar
  • 11
2 votes
2 answers
195 views

property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $G=(V,E)$ is the ...
CuriousChordalizer's user avatar

15 30 50 per page
1
3 4
5
6 7
260