All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
4 views

Shortest path on a hypergraph with no leftovers

In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by ...
3
votes
0answers
40 views

Understanding Dudley Chaining Argument for Rademacher Bound

I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
7
votes
1answer
164 views

Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
0
votes
0answers
23 views

Delaunay Triangulaition (or Voronoi) for a specific distribution of points

I found a paper about Delaunay triangulation for a set of points that are distributed by the Poisson distribution (https://pdfs.semanticscholar.org/9693/4b7e8e5483893f4874d7ba6afd812bbfe0ba.pdf). The ...
7
votes
1answer
195 views

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective? Are there any necessary ...
-1
votes
0answers
41 views

flip coin multiple times, see one head. then, how many tails in expectation? [closed]

Intuition says one, but my calculation by negative binomial distribution says two? I got very confused. Thank you!
1
vote
1answer
52 views

From Church-encoding to induction principle

I am looking for an algorithm to go from a Church-encoded datatype to their induction principle in the Calculus of Constructions. For example: ...
459
votes
70answers
163k views

What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
-1
votes
0answers
65 views

How Does Newton's Method Always Converge? [closed]

I've been working on some Stanford open courseware and right now I'm stuck on this homework problem. I was wondering if anyone could help. I can get everywhere before the horizontal pencil line but ...
0
votes
0answers
20 views

Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

I have just started on the book Elements of Programming (2019) and after thinking about the definitions for value types in chapter 1, that in principle seem to link meaning (the abstract entities of a ...
19
votes
1answer
8k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
0
votes
1answer
36 views

When can partial spectral sparsifiers be combined?

A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining ...
19
votes
2answers
1k views

Can we decide whether a permanent has a unique term?

Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \...
-1
votes
0answers
22 views

Maximizing some type of inner product

For positive integers $n,m,k$, you're given a vector $c\in\mathbb{N}^n$ and a set $\Omega$ of $k$ finite non-empty sequences of numbers from $\{1,\dots,m\}$. You're asked to choose $\sigma_1\lt\...
-2
votes
0answers
50 views

Weakest condition that connects $P=BPP$ and derandomizing $VV$

It is known $P=BPP$ is insufficient to derandomize $VV$ isolation lemma. What does it mean to be 'insufficient' here? Is there some theorem which says $P=BPP$ $+$ 'condition $A$' gives ...
-3
votes
1answer
86 views

is this selection problem np-hard? [closed]

Give $n$ clusters $C=\{C_i\}_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C_i=\{c_j\}_{j=1}^{|C_i|}$. The similarty between two points $c_i$ and $c_j$ is denoted as $w(c_i,...
4
votes
0answers
56 views

A reasonable proof strategy for formally verifying Ukkonen's algorithm?

What's a reasonable proof strategy to formally verify Ukkonen's algorithm in, say, Coq? The ingredients as far as I can tell would be: some form of separation logic to be able to reason about the ...
-4
votes
0answers
31 views

Circuit lower bounds or lower bounds related to non-$UGC$? [closed]

$UGC$ implies a lower bound on class $NP$. Are there lower bounds implied by failure of $UGC$? Vice versa do any lower bounds imply failure of $UGC$?
-2
votes
0answers
50 views

Are there connections between gaps in packing and covering LPs and UGC conjecjure?

UGC conjecture pretty much says the gaps obtained currently with SDPs are the best we can hope for. Packing and covering problems are typically cast as LPs and we get gaps in these. Are the gaps in ...
2
votes
0answers
24 views

Finding a minimal circuit basis for 3-uniform hypergraphs

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
1
vote
1answer
66 views

Extensional type theory and function extensionality

Is the principle of function extensionality $ (\forall x. f(x) = g(x)) \implies f = g$, derivable from ETT? Most notably is this derivable in Agda with axiom K?
6
votes
0answers
72 views

Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?

Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can ...
1
vote
1answer
72 views

Proof techniques for string algorithms?

I'm currently reading through the tome "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield, and I find the proofs to be extremely case analysis heavy and full of finicky +-1s. This seems ...
1
vote
0answers
42 views

Journals or conferences to submit formally verified libraries?

This is a soft question aimed at understanding whether there is any value to publishing formally verified libraries. I have formally verified (in Coq) implementations of: synthetic differential ...
-1
votes
0answers
17 views

Is it possible to just use one policy in a self-play setting? [closed]

I would like to ask is it possible to train an agent under self-playing setting but with just one policy to be trained? What are the foreseeable problems with such an implementation? My concern is as ...
0
votes
2answers
82 views

List of NP-Complete graph problems/ properties?

Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for ...
8
votes
0answers
96 views

Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one? By the usual one I mean the proof based on recursively querying whether there is a midpoint. ...
0
votes
0answers
37 views

Using martingale arguments to prove convergence of iterative algorithms

Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS? The examples I know of can only go so far as to show that there exists ...
-1
votes
0answers
36 views

Can a foreign computer securely be used to calculate an algorithm?

With data encryption (certificates) it's possible to use foreign computers (routers) for data transfer. A bad router cannot read the original data and if it manipulates the data the destination will ...
0
votes
0answers
24 views

Name for family of language classes closed under union, inverse gsm mapping and intersection with regular

Is there a name for language classes closed under union, inverse gsm mappings and intersection with regular languages? This is a bit similar to trio or AFL, but I specifically do not want to require ...
8
votes
0answers
105 views

Is Gödel's speed-up theorem an instance of Blum's speedup theorem?

Blum's speedup theorem is a statement about a certain class of computable functions for which it is always possible to find a faster algorithm. Gödel's speed-up theorem is a statement about the ...
222
votes
60answers
88k views

Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science": P = NP? The existence of one-way functions What are other major problems that should be added to this list? Rules: ...
1
vote
1answer
47 views

Reachability Query for Tree

What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $...
2
votes
2answers
152 views

Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
62
votes
5answers
2k views

Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
6
votes
2answers
254 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
8
votes
0answers
160 views

Which types are nihilistic?

[Note 2020-02-08: I updated the definition of nihilistic types so that it relies less on the type Empty.] A discussion on Twitter prompted the following question, ...
-1
votes
0answers
21 views

Applicability of M/D/1 queue for multi-class demand arrivals

Assume a queue system working as follows. Let $\lambda_i$ represent the Poisson demand rate for a customer class $i$ and $\mu$ represent the constant (deterministic) service rate. We have multiple ...
-4
votes
0answers
30 views

Exponentiation: Function Problem that must take exponential time? [closed]

Introduction The powers of 2 seem to be a sparse language. Because every time I see a power of 2 expressed in a binary-string the amount of 0-bits is always equal to $X$ in $2^X$. For example, 10000 ...
-1
votes
0answers
26 views

Complexity of solving systems of linear equations with hash preimages

Consider the following problem: Let $H$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients $$\boldsymbol A \...
-3
votes
0answers
28 views

What is the number of states in minimal dfa that accepts a bnary number divisible by 2 but not divisible by 3? [closed]

I am able to find out states in individual dfas but not after combining both. Can anybody solve this question please.
1
vote
0answers
16 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
0
votes
1answer
108 views

Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
3
votes
1answer
111 views

Is this greedy algorithm for vertex cover studied before?

For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms. The edge greedy (finding an edge and taking ...
1
vote
1answer
126 views

Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Background It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$. Although some natural problems are known to exist, many of them ...
1
vote
0answers
26 views

Minimum rank graph cut

Consider the following problem: Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle. Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
-2
votes
0answers
16 views

local tree-like structure of stochastic block model

For a stochastic block model $SBM(n, p, q)$, what conditions can we impose on $n, p$ and $q$ that for any given vertex $v$, the distance 2 neighborhood of $v$ would have tree-like structure?
2
votes
0answers
33 views

Family of functions with properties similar to k-wise independent hash functions

I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
4
votes
1answer
101 views

Semantic definition of strict positivity for a functor

If we consider a definition of recursive type as: F : Type -> Type; T = fix F; It is customary to talk about the functor F ...
11
votes
2answers
717 views

A game on several graphs

Consider the following game on a directed weighted graph $G$ with a chip at some node. All nodes of $G$ are marked by A or B. There are two players Alice and Bob. The goal of Alice (Bob) is to ...

15 30 50 per page
1 2 3 4 5 211