All Questions
12,315
questions
0
votes
0
answers
13
views
Difference between ''Optimization'' and ''Evaluation'' problem?
I have a question, regarding a definition that I found in the book ''Introduction to Linear Optimization'' (from ''Dimitris Bertsimas'' and ''John N. Tsitsiklis'' (1997), Page 517), regarding the ...
- 1
0
votes
0
answers
24
views
Reference for "A Turing machine cannot be equipped with an oracle for itself"
Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
- 757
3
votes
1
answer
66
views
Halting problem proofs that do not utilise self-reference or diagonalization
Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever?
All the duplicate questions I have come across end up ...
0
votes
0
answers
20
views
Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?
Let $N \ge 1$ be an integer and let $\mathfrak S$ be a nonempty collection of subsets of $[N] := \{1,2,\ldots,N\}$. For any $n \in [N]$, define $\partial_n \mathfrak S := \{S\setminus\{n\} \mid S \in \...
- 291
-1
votes
1
answer
56
views
notation in graph theory [closed]
I was reading a paper, and I found a notation that I don't understand:
$\mathbb{E}[| \textbf{S} |] $, where $\textbf{S}$ is a set. Are there any differences with the notation $\mathbb{E}[formula]$ (I ...
- 1
1
vote
0
answers
38
views
Open Quantum Analogs to Classical Problems
I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
- 111
0
votes
0
answers
28
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
1
vote
1
answer
43
views
Intuition behind UTT's internal logic
The "internal logic" of type theory UTT is defined in LF as follows:
What's the intuition behind this definition? I can kind of understand the declaration of the the first three constants - ...
- 135
1
vote
0
answers
23
views
Confusion about $T$ and $El$ when defining universes in LF
This is a technical follow-up question to Formulation of Tarski-style universes in LF
Consider LF, the logical framework used to define UTT (unified theory of dependent types). The next two quotes ...
- 135
2
votes
0
answers
38
views
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.
Let $\mathcal{P}$ denote the set of ...
0
votes
0
answers
30
views
Non regular distribution in [0,1] examples
We say a distribution is regular is its associated virtual function \psi(x) = x - (1-F(x))/f(x) is monotone non decreasing. Here F and f are CDF and PDF for the distribution.
How do I construct an ...
- 11
0
votes
1
answer
75
views
High-proba lower bound for $\prod_i \sum_{j\in G_i} z_j$, where the $G_i$'s are partition of $[n]$ with equal sizes, and the $z_j$'s are iid $\pm 1$
Let $n$ be a large positive integer and let $G_1,\ldots,G_k$ be a partition of $[n]:= \{1,2,\ldots,n\}$ it $k$ blogs of roughly equal size $n_1$. Let $x=(x_1,\ldots,x_n) \in \{\pm 1\}^n$ be a random ...
- 291
2
votes
1
answer
133
views
Examples for Real-time vs Linear time
A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
- 121
1
vote
1
answer
61
views
Formulation of Tarski-style universes in LF
Lately I've been asking questions on type theory on MSE, and I've been getting great answers, but I decided to give a try to this site and see if it will be helpful as well.
I'm looking at this note ...
- 135
0
votes
1
answer
27
views
+50
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
I'm working on a scheduling problem where I need to schedule a set of n weighted jobs that are partitioned into m groups, where ...
5
votes
2
answers
508
views
Find odd-ranked numbers from a list
From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?
I could sort the whole list using $O(n\log ...
- 113
3
votes
1
answer
92
views
Is there an established name for this kind of upper bound?
Assume for some algorithmic problem it holds that, for each $\epsilon>0$, there is some algorithm that needs space at most $O(n^\epsilon)$.
Is there an established name for this kind of bound?
I'd ...
- 1,417
1
vote
0
answers
32
views
Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube
Let $f: \{0, 1\}^n \rightarrow \mathbb R$ be a polynomial on the boolean hypercube. If $f$ is non-negative $(f \geq 0)$ i.e. $f(x) \geq 0, \forall x \in \{0, 1\}^n$ then $f$ always has a degree $2n$ ...
- 111
2
votes
0
answers
48
views
Efficiently checking that points lie on a polynomial
Say I am given $n$ points $y_1, …, y_n$ in a finite field, and want to check whether they lie on a polynomial $f$ of degree $t < n-1$ with $f(i)=y_i$. The obvious way to do this is to interpolate a ...
- 1,162
0
votes
0
answers
68
views
$NP \subseteq PSPACE$ proof clarification on enumeration of all solutions [closed]
I was asked to prove that NP is a subset of PSPACE using certificates (no reductions). It's incredibly obvious if you can iterate through every possible solutions of the problem in polynomial space, ...
- 109
4
votes
1
answer
448
views
Is classical lambda calculus grammar an `LL(k)` one?
I am playing with a lambda calculus and faced a question I find hard to reason about.
On the screenshot you may find the lambda calculus grammar. Is it an instance of the ...
- 214
3
votes
0
answers
75
views
Why do some problems seem to admit a richer family of algorithms than others?
Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
- 503
1
vote
1
answer
97
views
Communication complexity of equality on graphs
I came upon a nice observation in communication complexity, and I was wondering if it was already known.
Consider the following variant of the equality problem: There is a fixed graph $G$ that is ...
- 5,290
0
votes
1
answer
52
views
Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm
$\newcommand{\R}{\mathbb{R}}$
This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows:
Let $f : \{-1,1\}^n\to\R$ and let $\epsilon&...
- 51
1
vote
0
answers
47
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
0
votes
0
answers
26
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,039
0
votes
0
answers
32
views
Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT
3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction).
But, as I ...
- 304
1
vote
1
answer
61
views
If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl
I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is ...
0
votes
0
answers
47
views
Learning Parities via Gradient Descent
[Disclaimer: Crossposted in cs --> link]
In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [Kearn94] it ...
2
votes
1
answer
49
views
Balls in monochromatic bins
Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
- 23
-1
votes
0
answers
47
views
Probability of node being infected at time t=10 in SIR model
For the question above I am having a bit of a rough time trying to calculate the probabilities for nodes C, D, and E.
My thoughts:
For the node C I believe it would be equal to the probability that ...
- 1
-2
votes
0
answers
61
views
Is every decidable language Turing-recognizable? Please read body for more details
So I'm currently going through Michael Sipser's computational theory book. In chapter 3 he says this:
Call a language Turing-recognizable if some Turing machine recognizes it.
By recognizable it ...
0
votes
0
answers
34
views
Why $Rank(C)< R(k,d)$ for Depth 3 Balckbox PIT Algorithm implies $C$ is zero
I was reading the Survey on Polynomial Identity Testing by Nitin Saxena. In the Depth 3 Blackbox PIT Algorithm he first finds $O(k^2d^2+2^k)$ many subspaces of the linear forms of the $\sum\prod\sum(...
- 203
6
votes
0
answers
116
views
Consistent Sampling a Random Walk
Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid.
I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
- 898
2
votes
1
answer
89
views
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations.
I follow the proof of the following two identities :
$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
- 121
0
votes
0
answers
107
views
Is it known that P $\neq$ NP implies BQP $\neq$ NP?
Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
1
vote
0
answers
46
views
Is there a calculus or formalism for measuring set relations between algorithm outputs?
I'm asking this question from a fairly naive position, so apologies in advance, etc.
I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
- 111
2
votes
0
answers
72
views
What kind of solver should I use for this hypergraph problem?
I have to list the solutions to the following hypergraph problem:
There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
- 8,223
3
votes
0
answers
36
views
Can you compute Shannon expansion of a Boolean formula more efficiently by using a QBF solver?
Maybe this is not enough research level, but I've been scratching my head on it for a while...
I'm interested in the Shannon expansion of an existentially quantified Boolean formula of the form:
$$ \...
- 1,416
6
votes
0
answers
121
views
Consequences of $P^{NP[o(n)]} = P^{NP}$
I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$?
I ...
- 61
0
votes
1
answer
180
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
1
vote
0
answers
28
views
Non-uniform advice skews runtime
Let $\mathsf C$ be some class.
Let $a : \mathbb N \to \mathbb N$ be some function describing the bit length of advice.
Let $C/a := \{L | \exists L' \in \mathsf C \text{ and } \exists (w_n)_{n\in \...
4
votes
0
answers
71
views
Circuit computing Longest Increasing Sub-sequence (LIS)
Taking inspiration from sorting networks, I was wondering if another prominent algorithm can be implemented in the same fashion: finding the longest increasing sub-sequence (LIS),
Input is given as ...
- 679
10
votes
12
answers
4k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my third semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
- 117
6
votes
0
answers
69
views
Cycle packing with degree condition
Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?
Without the degree condition, the ...
- 113
4
votes
0
answers
57
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 209
2
votes
0
answers
29
views
Tape reduction, tape compression and time compression
In our lecture we have the following relationships:
I have problems to understand these abstract classes.
First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes.
DSPACE(...
- 21
1
vote
3
answers
216
views
Turing Machines and Logic
It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages.
Is there a logic over words (perhaps a nth order logic) such that it and turing ...
- 123
9
votes
1
answer
374
views
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Consider the following decision problem over a fixed alphabet $\Sigma$:
Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$
Output: does there exist a permutation $\...
- 8,223
7
votes
3
answers
914
views
Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?
Here is a Coq proof I've came up with:
...
- 214