All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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?
-2
votes
0answers
16 views

Loops Complexity

rfffffffffffffffffffffffffffffff
6
votes
2answers
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,...
1
vote
0answers
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 "...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
-2
votes
0answers
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?
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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. ...
2
votes
0answers
36 views

Does the awards budget cut problem support a sub $O(n\log n)$ time solution?

There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem. The problem gives you an input of $n$ integers called grants $g_1 ... ...
1
vote
0answers
24 views

What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix

Given a matrix, What is the computational complexity of the fastest algorithm to compute Jordan canonical form for the matrix?
-1
votes
0answers
55 views

What do we call a type system where any term of any type ultimately parses down to $*:\mathbf{1}$?

If a type system allows inductive types (as in e.g. Coq) then we can coin new primitive constants that inhabit types. For example $0:\mathbb{N}$ is constructed when defining $\mathbb{N}$ and does not ...
1
vote
0answers
25 views

Complexity Lower Bounds for 3D Sparse Gaussian Elimination

I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ...
3
votes
0answers
52 views

A class name for series-parallel graphs of same length

I'm currently working on graphs classes where the distance between two specific vertices is the same in every connected spanning subgraphs, and I am looking for a name for this class. Given a ...
0
votes
1answer
40 views

Knapsack problem with dependent weight and profits among the items

I'm working on a problem that may be reduced to the following variant of multiple knapsack problem: Each knapsack has its own valuation function; an item brings different profit and weight to a ...
6
votes
1answer
201 views

Reducing #SAT to MAJ-SAT

I once read in a paper: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm." What is the approach to this?
1
vote
1answer
48 views

Variable wire weights in DLOGTIME-uniform circuits

The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, ...
0
votes
0answers
70 views

What's the relevant CS theory for CodinGame challenges?

CodinGame challenges are basically extremely large decision trees, where your program is trying to find the node with the highest possible score. Greedy algorithms don't work because picking a locally ...
3
votes
1answer
80 views

Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
0
votes
0answers
28 views

Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph

tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
-1
votes
0answers
125 views

Are maximum independent set and minimum clique cover also cover-packing problems? [closed]

Maximum independent set and minimum edge cover are a pair of related problems and are cover-packing problems. (Also see p114 of West's Introduction to Graph Theory) Are maximum independent set and ...
0
votes
0answers
48 views

Are Graph Databases computationally equivalent to relational algebra [closed]

I am wondering if it can be shown that graph databases along with the graph database model and cypher queries are computationally equivalent to relational algebra. More specifically can cypher queries ...
-4
votes
1answer
21 views

Help find algorithm for array-based task

Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)? What is the solution? My solution is not ...
7
votes
3answers
304 views

Why should we believe that $NEXP \not \subset P/poly$

I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
3
votes
2answers
90 views

Tableau method for two-variable first-order logic

$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by ...
0
votes
0answers
42 views

A variant of randomized co-ordinate descent

Let us consider the following optimization problem. $\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
-3
votes
0answers
68 views

Complexity implications of impossibility of direct Diffie-Hellman compromise

Given generator $g$ of a multiplicative group mod a prime $p$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $g^x\bmod p$ and $g^y\bmod p$. The best way to solve this is through discrete ...
1
vote
0answers
55 views

Hardness of Approximation of Continuous Metric k-Median

First let me describe the metric $k$-median problem. Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...
-2
votes
0answers
70 views

How could we implemented orthogonality with Miranda, Haskell, Julia, Scheme, and Erlang languages? [closed]

How is orthogonality implemented with Miranda, Haskell, Julia, Scheme, and Erlang languages?
11
votes
0answers
295 views

NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
1
vote
0answers
36 views

Internal as well as external partition of (regular) graphs

Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an ...
1
vote
0answers
59 views

Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
4
votes
1answer
66 views

Context weakening as an explicit rule for languages of the the lambda cube?

I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in ...
-3
votes
0answers
39 views

A variant of the Generalized Assignment problem

There are two sets $T$ and $M$. The set $T$ represents a set of tasks and the set $M$ consists of machines. A task $t_i \in T$ has two attributes: 1) a minimum-finish requirement $R_{t_i}$ and 2) an ...
-3
votes
0answers
27 views

What changes the output on this black box?

We have a theoretical black box with no obvious inputs and outputs a value. For the sake of imagination, it's a literal black box with a digital counter on one side. We want to figure out what causes ...
0
votes
0answers
76 views

Optimal $\ell^1$ sketching, including the coefficient

Let us define the sketch as mapping $\varphi:R^D\to R^d$, such that for arbitrary $x\in\mathbb{R}^D$, its $\ell^1$ norm is preserved up to $\epsilon$ error, with $1-\delta$ success probability: $$\...
2
votes
0answers
39 views

Energy-Based Modeling vs Deep Learning

I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...
-3
votes
0answers
62 views

Lower bound for SAT

It occurred to me that if a given SAT is unsatisfiable, then a DPLL algorithm must try true/false settings for all literals to determine that there does not exist any satisfying literal combination. ...
1
vote
1answer
68 views

Dynamic transitive closure with immediate new reachability facts

The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, ...
-1
votes
2answers
91 views

Knowing if there are two solutions to the subset sum problem

I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ...
3
votes
1answer
208 views

Formalization of simulation for Turing machines

Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They ...
-1
votes
1answer
81 views

What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?

Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
7
votes
0answers
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 (...
1
vote
0answers
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, ...
3
votes
0answers
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 (...
9
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
2answers
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 ...
0
votes
0answers
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
1
2 3 4 5
222