All Questions
12,695
questions
3
votes
0
answers
137
views
On perm+1 and det+1
Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both.
...
- 12.8k
0
votes
0
answers
46
views
Deamortization of basic COLA (Cache oblivious lookahead array)
I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA.
The paper says that for every level k, for deamortization, ...
0
votes
0
answers
31
views
Natural communication problems that are hard only for number-in-hand protocols?
I am looking for tools to lower bound the deterministic, blackboard, number-in-hand communication complexity of a certain function which is roughly speaking $f : \{0,1\}^k \times \ldots \times \{0,1\}^...
- 205
2
votes
0
answers
77
views
Is universal hashing fully black-box reducible to error correcting code?
Fully black-box reduction is defined as in Notions of reducibility between crytpographic primitives, O. Reingold et al.
Error-correcting code is used in the black-box abstract way in the sense that ...
6
votes
1
answer
385
views
Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$
Can it be done in linear or at least subquadratic time?
- 13.6k
0
votes
0
answers
25
views
Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent
I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative ...
- 111
0
votes
0
answers
62
views
Why do we use Hoeffding inequality in UCB approach to drive the confidence set in multi-armed bandit problem?
In UCB algorithm, to drive the confidence set for unknown parameters we use Hoeffding inequality. I am wondering why we don't use Normal distribution instead which is much simpler to work with. Based ...
2
votes
0
answers
39
views
Space complexity of quantum algorithms for Subset sum
As far as I can find there are several quantum algorithms for the Subset sum problem with $2^{n/3}$ running time. Is there an algorithm with $2^{n/3}$ running time that uses much less space?
- 891
4
votes
0
answers
129
views
Complexity of numerical 3-dimensional matching where the three multisets are identical
Consider the following problem:
Input: one multiset $S = \{s_1, \ldots, s_n\}$ of positive integers written in unary
Output: can we build $n$ triples that sum to the same value, using each element of ...
- 8,916
2
votes
0
answers
36
views
Generalization of Binary Decomposition to Polynomials?
Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as
$$x = \sum_{i=0} x_i B^i,$$
where $x_i \in \mathbb{Z}/B\mathbb{...
- 918
20
votes
10
answers
3k
views
What are examples of recent relatively simple 'toolbox algorithms'?
Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc.
There are also several relatively standard data structures, such ...
2
votes
0
answers
42
views
Effective algorithms for finite lattices of (higher-order) monotonous functions?
I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
- 2,040
3
votes
2
answers
121
views
What is formal definition of non-deterministic algorithm in context of primitive/general recursion?
I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines.
What is the reference for non-deterministic ...
- 295
1
vote
2
answers
96
views
Do realizable systems always have some non-well-founded sets?
Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following:
LEM is not realized (e.g. this MSE answer)
The traditional ...
- 271
6
votes
1
answer
342
views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 958
3
votes
0
answers
73
views
Are there applications of Hyperbolic Programming other than Linear Programming and Semidefinite programming?
Title. It seems the most important special cases are LPs and SDPs. Are there other interesting special cases/applications for hyperbolic programming? (Apart from being super cool math on of itself)
I ...
- 1,088
3
votes
1
answer
98
views
Running time analysis of problems with a variable in problem definition
I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $[1,j]$-domination problem. Given a graph $G = (V, E)$, $n = |V|$, the problem ...
1
vote
0
answers
107
views
Real life application of two-way DFA
I am currently studying two-way DFA and I couldn't find and research anything on its real-life applications if there are any. I am very unsure where it could be used and any ideas would be great. tyia
- 11
0
votes
0
answers
51
views
Learning a PAC-lernable using agnostic-PAC framework
given H a family of functions which is PAC lernable such that for $\epsilon$ error and $\delta $ confidence interval it required $m(\epsilon,\delta)$ samples.
I understood that if we learn H under ...
7
votes
1
answer
403
views
What kind of resolution is CDCL corresponding to?
For an unsatisfiable CNF instance, CDCL will return a resolution refutation.
My question : what kind of resolution does it return? tree-like, regular or general?
- 315
0
votes
0
answers
30
views
Decidability of Mixed-Integer Semidefinite Programs
Semidefinite programs (SDP) have an "efficient" solution, as a convex problem, by e.g. the ellipsoid method; but this comes with standard caveats as the output can be exponentially long (...
- 807
2
votes
1
answer
99
views
Shortest Common Supersequence of Permutations
For integers $k$ and $n$, let $P_{k,n}$ be the set of all size-$k$ sets of permutations of $[n]$.
The Shortest Common Supersequence for Permutations (SCSP) problem is:
given a set $S\in P_{k,n}$, ...
- 185
-1
votes
1
answer
87
views
How is memory being used by an algorithm, to define its space complexity? [closed]
In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
- 99
0
votes
0
answers
58
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
- 1,177
1
vote
0
answers
45
views
Compute Fourier coefficients from Single Fourier coefficient and initial vector?
I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single ...
- 918
3
votes
0
answers
92
views
I am looking for a detailed list of known reductions of NP-Complete problems
I am looking for a detailed list of known reductions of NP-Complete problems. Much like Richard Karp's list of 21 NP-Complete problems has more than a dozen reductions, I am looking for a bigger ...
1
vote
0
answers
72
views
Using a certificate in the proof of NP hardness
Say I wanted to determine that the problem of membership in some language $L \subseteq \{0, 1\}^*$ is NP-hard. Say that I have a reduction $r: \{\text{set of quantifier free formulas} \rightarrow \{0,...
- 21
2
votes
0
answers
78
views
Status of QNC vs. PSPACE
It is known that $\text{NC} \neq \text{PSPACE}$, now I am wondering if there is a similar separation for $\text{QNC}$, the class of decision problems solvable by polylogarithmic-depth quantum circuits ...
- 900
7
votes
1
answer
187
views
Can you regain the Church-Rosser property in languages with continuations?
I'm aware that if you naively add continuations to a language, the Church-Rosser property no longer holds. For example, suppose we have some variant of the STLC with basic arithmetic and integer types....
- 81
6
votes
2
answers
610
views
NP-complete problems where the inputs are prime numbers
Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
- 161
5
votes
1
answer
154
views
Functions with polytime iterated applications
Definitions
Let $f : \{0,1\}^n \rightarrow \{0,1\}^n$ be some boolean function where the length of the output always equals the length of the input. Let $f^{k} : \{0,1\}^n \times \mathbb{N} \...
- 1,204
1
vote
1
answer
46
views
What is known about the complexity of Network Diversion?
In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
- 576
0
votes
1
answer
56
views
complexity of the maximum rank correlation
Given two sets of vectors of dimension $p$, $x_1,\ldots,x_m$ and $y_1,\ldots,y_n$, The Maximum Rank Correlation estimator is the vector $\beta$ given by $$\arg\max_{b\in\mathbb{R}^p}\sum_{i=1}^m\sum_{...
- 1
5
votes
1
answer
148
views
Finding $k \times k$ rectangle in a matrix with maximum sum
Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$
I expect the problem to be NP-hard, so I want a polynomial ...
- 151
7
votes
0
answers
191
views
Relationships between Descriptive Complexity and Average Case Complexity
Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
- 1,181
0
votes
2
answers
33
views
Combining different length epsilon-ADU hash function families
For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that
for any distinct $m, m' \in M$...
- 720
0
votes
0
answers
42
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
- 101
2
votes
0
answers
72
views
Proof systems that may be stronger than extended Frege?
The extended Frege proof system is thought to be a fairly strong proof system, with no known superpolynomial lower bounds. But I wonder, if extended Frege is proved not to be polynomially bounded one ...
- 177
4
votes
1
answer
85
views
Independent set queries with preprocessing
Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
- 464
3
votes
0
answers
205
views
Is the Fueter-Polya Conjecture proven
The Fueter–Pólya conjecture states that if $\pi$ is a polynomial function and a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ then $\pi$ must be the Cantor pairing function ($(x,y) \mapsto 1/2(x + y)(...
- 149
0
votes
1
answer
67
views
What's the exact complexity of a DFS if we revisit nodes?
By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
- 13
-1
votes
1
answer
74
views
Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$
I am able to solve this using brute force but curious if there is a better approach.
Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
- 1
0
votes
0
answers
20
views
The minimal number of messages required to solve the mutual exclusion problem in a symmetric distributed system
In the seminal paper introducing their namesake algorithm for solving the mutual exclusion problem in a distributed system, Ricart and Agrawala assert (in the first paragraph of section 4 Message ...
- 354
-1
votes
1
answer
124
views
Locally nameless representation implementation
ORIGINAL: I am programming a functional compiler and found out about locally nameless representation (using de brujin indeces for bound variables and names for free variables). I just don't understand ...
- 9
2
votes
1
answer
102
views
clique problem in graphs with bounded degree
Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
- 23
4
votes
1
answer
103
views
Implicit characterization of sublogarithmic space
Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine ...
- 1,204
13
votes
2
answers
665
views
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Definition. A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability.
Question. The notion of a ...
- 133
0
votes
0
answers
35
views
Using an offline approximation algorithm within an online algorithm
When defining an online algorithm, it is common to assume that there exists an optimal offline algorithm to be used over the set of already known requests.
For example, consider the IGNORE algorithm ...
0
votes
0
answers
65
views
Construction of a PDA for the binary and decimal representation of a number
I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way?
Problem:
Given $n \in \mathbb{N}^+$. ...
- 11
3
votes
1
answer
174
views
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.
For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:
It is ...
- 33