All Questions
12,402
questions
-3
votes
0
answers
53
views
Why isn’t BQP in SZK?
It has been proven that $BQP \not\subset SZK$ (see p7 of this paper).
On the other hand, Vadhan’s thesis on complete problems for SZK presents an easy reduction for why $BPP \subset SZK$ (Proposition ...
-3
votes
0
answers
27
views
What uniformity is assumed in the statement $P=NP$?
We usually say $P=NP$ is impossible. What uniformity is assumed in the statement $P=NP$? Is it possible $P=NP$ with $Logspace$ uniformity but not with $DLogtime-AC^0$ or even $NC^1$ uniformity? What ...
- 12.6k
1
vote
0
answers
32
views
Proving existence of efficient PAC learning algorithm without noise info given poly-time algorithm with noise upper bound
How would I prove that if there is an efficient algorithm for PAC learning in the presence of classification noise by an algorithm that is given a noise rate upper bound $\eta_0$ ($1/2 > \eta_0 \...
- 111
4
votes
1
answer
116
views
Does being able to efficiently factor semiprimes allow to efficiently factor any integer?
The Wikipedia page about Shor's algorithm currently contains the following sentence:
A complete factoring algorithm is possible using extra classical methods if $N$ is a semiprime, that is, if it is ...
- 142
6
votes
0
answers
93
views
What is the Simplest type of automaton that can simulate all DFAs?
During recent research in a somewhat unrelated field (Spin Physics), I stumbled across a subclass of regular languages. The context of the research poses the question what the minimal power of the ...
- 167
0
votes
0
answers
28
views
How do I estimate the motion of a rigid body from a sequence of images?
I have just recently started studying computer vision, and I wanted to find ways to compute the translational and rotational motion from a sequence of images alone. Could someone explain how this ...
- 1
0
votes
1
answer
51
views
Finding the shortest cycle containing a vertex in a graph
Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to ...
2
votes
1
answer
220
views
6-regular graph without small 3-regular subgraph
My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 6-regular graph that does not have small 3-regular subgraphs. For example, I ...
0
votes
1
answer
103
views
What are advantages of bigraphs?
I would like to know if there are any limitations of frameworks such as Petri nets (with its extensions) or pi-calculus that bigraphs developed by Robin Milner do not have.
If there are none, then ...
- 101
1
vote
1
answer
131
views
Which are the rules for minimal logic in both sequent calculus and natural deduction styles?
Are there any references I could use which explictly contain the rules for minimal logic, both as a sequent calculus and in natural deduction? (Doesn't need to be the same reference for both!)
To give ...
- 337
1
vote
0
answers
25
views
What is the complexity of the "characteristic bisection" method?
The characteristic bisection method is an algorithm for finding approximate zeros of multi-dimensional functions. It is a generalization of the bisection method; it is described briefly here.
...
- 1,922
0
votes
0
answers
24
views
How to calculate processor throughput boundary in CSAPP?
In Chapter 5.7 of CSAPP, author list out the throughput boundary of Intel Core i7 Haswell while executing the operation Integer addition and multiplication, floating points addition and multiplication....
- 1
5
votes
1
answer
99
views
Logical Equivalents of Finite State Transducers
There's a notion of "regular" function on words in automata theory that corresponds nicely to functions in WS1S/Büchi Arithmetic/the logic of words with a prefix and equal-length relation. ...
- 259
3
votes
0
answers
70
views
Is there an algorithm for reducing the average row width of a sparse matrix?
Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be:
$$w_i \equiv r(A_i) - l(A_i),$$
where $r(A_i)$ is the index of the rightmost nonzero element ...
- 31
3
votes
0
answers
54
views
State-based vs. transition-based definitions of alternating automata
Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.
Alternating finite automata (AFA) are usually defined in modern literature in the following terms. An ...
- 1,446
3
votes
0
answers
49
views
How does extended resolution p-simulate extended Frege?
I found a slide stating that "extended resolution and extended Frege p-simulate each other", without providing a proof. It's obvious that extended Frege p-simulates extended resolution, but ...
- 31
-1
votes
0
answers
53
views
Bin packing with variable size bins
Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$ and bin capacities $b_1,\dots, b_n \geq 1$. The task is to pack the items in as a few bins as possible such ...
7
votes
0
answers
224
views
Determinant Computation
Let $A \in \mathbb{N}^{n \times n}$ be a skew symmetric (antisymmetric) matrix such that for all $i,j \in [n]$ it holds that $A_{ij} = 2^{k_{ij}}$ for some $k_{ij} \in \{0,1,\ldots, 2^{n}\}$. That is, ...
- 103
2
votes
1
answer
87
views
Complexity of computation of ANF-form (Zhegalkin polynomial)
Let $f: \mathbb{F}_2^n \to \mathbb{F}_2$ be a boolean function.
Consider $f$ as a multilinear polynomial over $\mathbb{F}_2$ (algebraic normal form or Zhegalkin polynomial).
How hard is to define the ...
- 1,881
0
votes
1
answer
54
views
Exchange cards with sum requirement
Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
- 123
0
votes
0
answers
78
views
Parallel repetition to amplify the gap for nonlocal games
Suppose for an one-round nonlocal game $G$ with question size $n$, answer size $2$ (i.e the answer is yes or no), a verifier and two provers Alice and Bob sharing $\text{Poly}(n)$ entangled-qubits. ...
- 51
2
votes
0
answers
44
views
Invertible function with hard to find collisions in the Random Oracle Model
This question is inspired by this tweet. I discussed this with some people at my institution when this came out and came to the conclusion that this was probably possible using lattice-based ...
- 121
0
votes
0
answers
56
views
Number of quantifier alternations in prenex form of a formula
I'm currently studying hyperlogics and in particular HyperLTL/CTL*.
In model checking algorithms for such logics the number of quantifier alternations appearing in a formula can play an important role ...
4
votes
0
answers
55
views
(Where) in the polynomial hierarchy is determining the mixing time of an implicitly defined graph?
Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
- 957
0
votes
0
answers
71
views
The difference between the 1st and 2nd editions. "Compilers Principles, Techniques, and Tools" by Aho, Sethi and Ullman
I bought "Compilers Principles, Techniques, and Tools 1st Edition" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman long years ago and it has been sitting on my bookshelf ever since.
I ...
- 101
4
votes
1
answer
146
views
Pumping lemma for CFL intersection
The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages....
- 303
2
votes
0
answers
91
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 768
1
vote
0
answers
36
views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers.
In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 484
3
votes
0
answers
60
views
What's the difference between "modular" and "compositional"?
When talking about reducing complexity in a software system, we often talk about making it "modular" by breaking it up into multiple modules that are all linked together to form the overall ...
1
vote
0
answers
72
views
$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]
We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
- 268
-1
votes
1
answer
52
views
Typing rule for corresponding `val` and `let` bindings
$\newcommand{\clet}{\texttt{let }}
\newcommand{\cval}{\texttt{val }}
\newcommand{\cin}{\texttt{ in }}
$I have the syntax for a programming language containing both let-bindings of the form $\clet x = ...
1
vote
1
answer
47
views
Is $GapCVP_{\gamma} \in coAM$ for all $\gamma$?
In this lecture Regev introduced the Goldreich-Goldwasser protocol (start of page 2) to show that $GapCVP_{\sqrt{n}} \in coAM$. The protocol is really intuitive, but I don't really understand why he ...
- 13
0
votes
0
answers
85
views
When the tree-like resolution size is the same with general(regular) resolution size？
Background:
For an unsatisfiable SAT formulas, the length of a resolution refutaion means the number of clauses in it.
It's well known that there exist exponential separation between tree-like and ...
- 21
1
vote
1
answer
72
views
Why is SVP not in coNP if Gram Schmidt Orthogonalization can provide us with a lower bound of the shortest vector
From https://cbright.myweb.cs.uwindsor.ca/reports/cs667proj.pdf
More precisely, the decision version of the poly(n)-unique SVP problem lies in NP and coNP. This means
that given a lattice and a ...
- 113
2
votes
0
answers
117
views
Property testing for membership in span of vectors
Notation
Let $\mathbb{F}$ be a finite field, and $m, n$ be natural numbers.
An algorithm $A$ is said to have oracle access to a vector $v \in \mathbb{F}^n$ if it can query $v$ with input an index $i \...
- 109
2
votes
0
answers
47
views
Convert regular tree expression to tree automaton
Is there a polynomial time algorithm to convert a regular tree expression to an equivalent tree automaton? Does it matter whether the automaton is required to be deterministic?
I found two papers that ...
- 929
7
votes
0
answers
188
views
Found a mistake in a paper - should I be mentioned?
I'm a graduate student, and I found a mistake in someone's paper, from the arxiv version.
It's a mistake in a certain proof, so that their proof didn't actually prove the theorem. I pointed it out to ...
- 71
3
votes
1
answer
241
views
Model foreign keys as dependent types?
A database consists a list of tables. For example you have a table of Worker and a table of Project where each project needs a ...
- 347
13
votes
1
answer
193
views
Combinatorics of a badminton tournament
Someone wants to organize a badminton tournament, where each match is a 2 versus 2, i.e. by teams. The idea is to have teams rotate, so that you can play with everyone.
If there are $n$ players, where ...
- 8,473
4
votes
1
answer
159
views
Computing an approximate root of a two-dimensional monotone function
Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
- 1,922
2
votes
0
answers
50
views
Intermediate problems between $CC^0$ and $ACC^0$
Definitions
$CC^0[m]$ is the set of languages decidable by constant-depth polynomial-size circuits consisting only of unbounded-fanin $MOD_m$ gates. We write $CC^0$ to mean the union over all $m$. $...
- 1,034
0
votes
1
answer
146
views
How do you achieve linear time complexity of greedy graph coloring?
In most resources I could find, greedy algorithm is described as follows:
for every vertex $v$, assign the minimal color not used by its neighbors.
The above could be implemented as:
...
6
votes
0
answers
73
views
Time hierarchy for one-tape Turing machines
The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape ...
- 303
0
votes
0
answers
43
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
3
votes
0
answers
24
views
(Classical) Zero Knowledge protocol with quantum poly time simulator
We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these ...
- 31
0
votes
0
answers
52
views
How to find upper bound on regret of stochastic linear bandit not pseudo-regret
In stochastic linear bandit we assume that the reward at each period is generated from $r_t= x_t^\top \theta + \varepsilon_t$ where $\varepsilon_t$ is R-sub-Gaussian. Based on this definition, we ...
- 61
2
votes
0
answers
71
views
What is the time complexity of fermionic Fourier transform?
Suppose $N = 2^L$ and we are interested in performing the following transformation a $\mapsto$ a_hat on arrays of $N$ complex ...
- 121
1
vote
0
answers
65
views
Do soundness and completeness need to be exact converses of eachother?
This question concerns the derivational soundness and completeness of the first-order proof system LK (without equality) as presented in Logical Foundations of Proof Complexity by Cook and Nguyen. In ...
- 201
1
vote
1
answer
67
views
Why isn't the proof obtained using Buss's proof of the derivational completeness of LK anchored?
The version of Buss's proof I'm referring to is the proof of Lemma II.2.24 in Logical Foundations of Proof Complexity by Cook and Nguyen. In the interest of keeping this question self-contained I've ...
- 201
0
votes
0
answers
22
views
Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits
I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka
In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$
We have $C|_V$ which is ...
- 268