# All Questions

11,092 questions
Filter by
Sorted by
Tagged with
9 views

### Quantum complexity of TQBF

There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits?
16 views

### Loops Complexity

rfffffffffffffffffffffffffffffff
58 views

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below: The original algorithms,...
16 views

### “Interesting” categories whose internal logic is a dependent-linear type theory

Dependent-linear type theories may be a functional programmer's dream, but is it categorically interesting, i.e. is it the internal language of an "interesting" category? By "...
16 views

### Dimentionality Reduction for Lp-Normed Spaces

Are there any dimensionality reduction techniques known for the general $\ell_{p}$-normed spaces for $\ell \geq 1$? In the Euclidean space, there is a classical result: Johnson-Lindenstrass lemma that ...
57 views

### NLOGTIME versus $\exists$DLOGTIME

$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
29 views

### Algorithm checking if a given string defines a valid term of any type

In a type theory where type checking is decidable we can algorithmically determine whether a given a string defines a valid term of any type. But what about other type theories?
41 views

### Comparision of two ML models

Let's say I have two models trained to do the same thing (EDIT : Clarification here, trained to do the same thing implies they were models trained to solve the same problem (for eg - two different ...
52 views

### Is Scheme language orthogonal? [closed]

I want to know Scheme language is orthogonal or not, and if yes, then which are the features that make it orthogonal. How can we determine a language is orthogonal or not? and the benefits of ...
26 views

### Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]

I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
36 views

81 views

### Is it possible that feedback vertex set problem has an $O(k^2/\log k)$ kernel？

(This question also suits for other similar natural $\mathrm{NP}$-hard problems) I know that there is a $4k^2$ vertex kernel (and $8k^2$ edge kernel) by Thomasse [Thomasse09] for Feedback Vertex Set (...
198 views

### Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
62 views

### Suffix array construction algorithms (SACAs)

I am working on an efficient pattern-matching algorithm (using binary files as input) based on suffix arrays. I would like to ask you If you are familiar with any suffix array construction algorithm (...
85 views

### What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
101 views

### When does a bipartite graph have bounded treewidth?

As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth? More generally, I would like to ...
213 views

### Intuition behind nested positivity and counterexamples

I'm looking at the nested positivity conditions for inductive types stated in the Coq manual. First off, are there any other references (not necessarily for Coq, but in dependent type theories ...
33 views

### Online Weighted Allocations to Simulate a Distribution

I have a seemingly simple task that I want to solve using an online algorithm but unfortunately I wasn't able to find relevant resources even though it seems so basic. The inputs are \$D=(d_1,\dots,d_m)...

15 30 50 per page