All Questions

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 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 ...
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 - ...
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 ...
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 ...
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(...
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 ...
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 ...
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 ...
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, ...
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(...
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

15 30 50 per page
1
2 3 4 5
247