All Questions

Filter by
Sorted by
Tagged with
-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 ...
Irna Mosa's user avatar
-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 ...
Turbo's user avatar
  • 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 \...
aome's user avatar
  • 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 ...
glS's user avatar
  • 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 ...
Thomas Tappeiner's user avatar
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 ...
Harkais's user avatar
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 ...
Sharp Edged's user avatar
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 ...
Balchandar Reddy's user avatar
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 ...
zajer's user avatar
  • 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 ...
paulotorrens's user avatar
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. ...
Erel Segal-Halevi's user avatar
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....
陳柔妍's user avatar
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. ...
TomKern's user avatar
  • 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 ...
Germ's user avatar
  • 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 ...
gigabytes's user avatar
  • 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 ...
Soha's user avatar
  • 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 ...
TheCollegeStudent's user avatar
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, ...
John's user avatar
  • 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 ...
Alexey Milovanov's user avatar
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$...
TZM's user avatar
  • 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. ...
qmww987's user avatar
  • 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 ...
Bolton Bailey's user avatar
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 ...
timtombobjohn's user avatar
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 ...
Mark S's user avatar
  • 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 ...
tchappy ha's user avatar
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....
QMath's user avatar
  • 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 \...
delete000's user avatar
  • 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 ...
Naysh's user avatar
  • 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 ...
Jonathan Schuster's user avatar
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)},\ \...
Soham Chatterjee's user avatar
-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 = ...
llilibbou's user avatar
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 ...
kerf's user avatar
  • 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 ...
Jxb's user avatar
  • 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 ...
bubakazouba's user avatar
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 \...
Pratyush Mishra's user avatar
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 ...
user1868607's user avatar
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 ...
User's user avatar
  • 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 ...
molikto's user avatar
  • 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 ...
Denis's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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$. $...
Jake's user avatar
  • 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: ...
Sebastian Szczepański's user avatar
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 ...
QMath's user avatar
  • 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 ...
bcarlborg's user avatar
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 ...
vk19's user avatar
  • 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 ...
Amin's user avatar
  • 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 ...
fiktor's user avatar
  • 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 ...
Johnny's user avatar
  • 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 ...
Johnny's user avatar
  • 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 ...
Soham Chatterjee's user avatar

15 30 50 per page