All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
20 views

Oracle separation between coNP and QMA implies oracle separation between NP and QMA

In [this] paper, Aaronson remarks (page 2, footnote) that: From the BBBV lower bound for quantum search [6], one immediately obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
6
votes
2answers
293 views

On the complexity of a “list” datastructure in the RAM model

I am interested in the complexity of a data-structure equipped with the following operations (similar to a list): insertion of an element at a given position within the list deletion of an element at ...
62
votes
10answers
7k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
5
votes
1answer
438 views

Factoring with LLL when the form of the factors is given

Given a degree $2k$ reducible polynomial $$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$ with $$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(...
-2
votes
0answers
33 views

Smallest Bicubic Graph without a Hamilton Path [closed]

I found a lot literature in the net about graphs without hamiltonian cycles but I can't find the Smallest Bicubic Graph without Hamilton Path I also don't care about planarity or connectivity. ...
2
votes
1answer
84 views

Additive versus multiplicative accuracy

I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is ...
0
votes
0answers
30 views

Different version of approximation complexity and algorithm for densest-k-subgraph problem

In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
-1
votes
0answers
18 views

Verification in the context of TLA+ compared to CSP

While reading through the paper - Composition: A way to make proofs harder, Lamport sets up the argument that it is better to reason about computational systems directly using mathematical elements ...
-4
votes
0answers
40 views

Garbage collection and halting problem [closed]

I'm trying to understand a concept in theoretical computer science and I had a general (theoretical) question about carbage collection. Why isn't it possible for a garbage collector to free memory for ...
2
votes
2answers
605 views

Which formalism is best suited for automated theorem proving in set theory?

Abbreviations - FOL is first-order logic; NBG is Von Neumann–Bernays–Gödel set theory; SEP is Stanford Encyclopedia of Philosophy; HOL is higher-order logic; ATP is automated theorem proving. Context ...
6
votes
1answer
280 views

An axiom for John Major's Equality

In the the standard library of Coq, there is the axiom: Axiom JMeq_eq : forall (A:Type) (x y:A), JMeq x y -> x = y. Why isn't it provable? Can it be reduced ...
1
vote
1answer
82 views

Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
1
vote
1answer
102 views

Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
3
votes
0answers
57 views

Fastest known algorithm to enumerate k-cliques in a graph for fixed k

Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ? The time-complexity of the ...
0
votes
0answers
48 views

Query complexity for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$

I'm studying query complexity and I'm trying to understand Bernstein-Vazirani's problem (https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm) and Simon's problem (https://en.wikipedia....
3
votes
0answers
26 views

Is Rackoff's bound on the length of shortest covering executions in VAS still the best known one?

In 1976–1977, Rackoff proved in The covering and boundedness problems for vector addition systems that the length of a shortest covering sequence in a VAS is bounded by $2^{(3n)^n} = 2^{2^{(\log_2 3)n\...
0
votes
0answers
16 views

ANN for 2D-Coordinate Classification

I have a dataframe of spatial data where X- and Y-Coordinates and the belonging of these coordinates to territorial units are given. Now I would like to train an ANN to classify coordinates to the ...
0
votes
1answer
68 views

Can a result of (any) hash algorithm contain the hash result itself?

Suppose you have a file of 240 lines. Any lines, any content. You then calculate the hash of that file, let's say MD5, and the result is something in the following structure: ...
5
votes
0answers
111 views

Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
5
votes
1answer
117 views

Topological sorting of a DAG where special vertices have to come in even groups

Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
8
votes
0answers
115 views

Tree decompositions of optimal width where every vertex is in a bounded number of bags?

Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$. Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible ...
1
vote
1answer
188 views

Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?

The paper https://cs.brown.edu/people/seny/pubs/vbponline.pdf discusses $\{0,1\}$-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the ...
2
votes
0answers
40 views

Is black box parallel quantum speedup ever nontrivial?

Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries. Are there any oracle problems where quantum ...
-5
votes
1answer
20 views

Polynomial-time reducibility of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
4
votes
0answers
88 views

Non-trivial existence proof in type theory

What are some examples of existence proofs in Coq/Agda etc., where the constructed natural number is useful from mathematical point of view, but it's non-obvious from the proof what it should be? I am ...
30
votes
7answers
3k views

Lipton's most influential results

Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize "for Introduction of New Ideas and Techniques". What are to your minds the main new ideas and techniques that Lipton ...
0
votes
0answers
35 views

Would a machine learning algorithm benefit from an “optimization oracle”?

I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard. Now let'...
1
vote
0answers
48 views

Multiplicative-depth 1 composition of arithmetic circuits

I am trying to find information about the following problem. Let $C_1$ and $C_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic ...
2
votes
0answers
79 views

Running time of Tarski Quantifier Elimination

I'm looking for some formula/expression in a citable resource, that gives the running time for Tarski's quantifier elimination. In my search, I only found the statement "it's not elementary" on ...
9
votes
1answer
145 views

What is the best upper bound on the running time of the graph minor algorithm?

A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
-3
votes
0answers
25 views

Simplify proof writing with in tactics in coq

I am beginner in Coq and trying to do some exercises. One issue I have is that I often find the proof, but the proof writing style seems to be sub-optimal Here is an example below: ...
-1
votes
2answers
680 views

Is there any way to differentiate between “sort of” Turing-Complete and “really” Turing-Complete?

Some things, like the computer language C, turing machines, lambda calculus, etc. seem to be "naturally" Turing-Complete. That is, they're just Turing-Complete from the bottom up. On the other hand, ...
-4
votes
0answers
90 views

Rigorous evidence for difficulty of sub-half exponential lower bound

Razborov provided rigorous evidence for non-natural proof necessity for superhalf-exponential lower bound for Discrete logarithm problem. Is there any rigorous evidence for difficulty of super ...
6
votes
1answer
492 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
29
votes
2answers
825 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
0
votes
0answers
40 views

understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
2
votes
1answer
74 views

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
1
vote
0answers
68 views

At most how many satisfying assignments are there for a 2SAT with n variables?

It is not obvious but easy to see that, for some fixed set of satisfying assignments, there is no 2CNF that can satisfy the set of satisfying assignment exactly, when I discover this, I wonder at most ...
1
vote
1answer
36 views

Constructing Orbits of the Automorphism of a Graph Group in Bliss

I'm using the Bliss package for graph isomorphism and canonization. The program is working great for the type of graphs I'm interested in. In one of the applications I need to compute the orbits of ...
23
votes
4answers
11k views

How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...
1
vote
1answer
60 views

How to prove that Supremum preorder coincides with Hoare preorder?

Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$. I mean: Hoare ...
17
votes
2answers
3k views

A total language that only a Turing complete language can interpret

Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind ...
1
vote
1answer
33 views

Sampling from a family of hash functions, not uniformly at random?

Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we ...
0
votes
1answer
77 views

Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $X \sim p(x)$ and a quantized codebook $\...
6
votes
1answer
683 views

Algorithm for finding a 3-cycle cover

Given: An undirected, unweighted graph Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges Is there any algorithm that solves this problem, possibly with some ...
78
votes
9answers
9k views

Are research papers hard to read?

This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO). I find research papers on computer science hard to understand. Of course the subjects are ...
7
votes
0answers
104 views

How to succeed in remote TCS research as undergraduate

I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
0
votes
0answers
26 views

Encrypt an explicit circuit

Suppose we are given a circuit that are promised to be in a fixed class $\mathcal{C}$ (say AC^0). We want to “encapsulate” the circuit such that the resulting circuit computes the same function, while ...
-3
votes
0answers
20 views

What is the difference between the competitive ratio of a LRU cache with n ≫ k and n = k + 1?

In caching problem, the total number of pages is n, the size of the cache is k pages, and the total number of requests is T. Suppose we request completely random pages from 1 to n and we use LRU ...
4
votes
1answer
88 views

Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?

Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks: A node can lose at most one child. Once that child is lost, the node must be cut from its parent. ...

15 30 50 per page