All Questions
1,809 questions
0
votes
0
answers
118
views
sparsest cut always has solution
Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
- 1
1
vote
1
answer
640
views
Approximate Set Cover Problem by Rounding
Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets $S$ for ...
3
votes
3
answers
2k
views
Problem regarding subsets that sum to 0
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...
5
votes
1
answer
780
views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
- 96.4k
2
votes
1
answer
130
views
Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?
Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming.
A famous application of semidefinite ...
- 2,383
1
vote
0
answers
538
views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
1
vote
2
answers
2k
views
equivalence of NL Definitions
Hi,
How to prove that the two definitions of the complexity class NL are equivalent.
1st definition is with a non deterministic logspace TM, and the second is with a deterministic logspace verifier ...
- 11
11
votes
2
answers
746
views
Ordinals and complexity classes
What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...
- 6,819
0
votes
1
answer
409
views
Need help to find an efficient algorithm for the following problem!
Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.
Given $A_{n\times n}$ is the covariance matrix of $x$.
$u$ is a given n-dimensional vector of real ...
- 131
7
votes
2
answers
955
views
Distribution of the computable numbers on the real number line
If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
- 71
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
3
votes
1
answer
397
views
Partially optimal solutions in integer linear programming
Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals.
An other interesting ...
- 567
9
votes
2
answers
807
views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
2
votes
2
answers
837
views
Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph
Hi everyone!
This is my first post, apologies if I made any mistakes anywhere.
Here goes the question:
Consider all length 7 binary sequences.
Let $X$ be the set of sequences with hamming weight 3 ...
- 360
4
votes
1
answer
344
views
A regular n,2d graph is a good expander.
Context
Reading about Expanders
Setup
A regular n,2d graph is generated as follows:
generate d random permutations of [n]
connect the edges; giving a n,2d regular graph
...
6
votes
1
answer
3k
views
Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value
Setup
Let $A$ be a stochastic matrix.
Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$.
Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$
Question:
...
2
votes
1
answer
153
views
Structure of class P
Hi all,
1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the ...
- 151
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
2
votes
0
answers
917
views
Guessing game with guess cost
This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
- 4,952
6
votes
2
answers
426
views
Complexity of detecting a convex body in $\mathbb{R}^n$?
Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,
$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The ...
- 111
15
votes
7
answers
3k
views
Compressing Graphs (Kolmogorov complexity of graphs)
What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
user3409
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 19.2k
25
votes
1
answer
6k
views
Evidence for integer factorization is in $P$
Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
- 800
1
vote
1
answer
257
views
Pseudorandom Generator vs Constant Depth Circuits / Branching Programs
Hi.
I am looking for a survey on the state of the art in pseudorandom generators vs
(1) constant depth circuits
and/or
(2) Branching Programs
For (1), is "Anindya De, Omid Etesami, Luca Trevisan ...
6
votes
2
answers
2k
views
P vs NP and OWFS
It is known (simple HW exercise) that:
If P = NP, that OWFs (one way functions) can not exist.
It is also known that there is a Universal OWF:
namely, there is a function f:
s.t. if any OWF ...
4
votes
1
answer
985
views
Complexity of bipartite graphs and their matchings.
My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...
- 17.6k
4
votes
1
answer
4k
views
Finding a vertex of least distance to all other vertices in a graph
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...
3
votes
1
answer
386
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 77
0
votes
0
answers
138
views
Bounds on reducing from NP to SAT
Let M be a non deterministic turing machine.
Suppose M is a TM that runs in T(n) time.
Given an instance of x in {0,1}^n, and the question M(x) accepts?
We can
1) convert M into an oblivious TM ...
- 19
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151
4
votes
0
answers
213
views
Suppose P = BPP; Pseudorandom Generators vs NP Adversary
Suppose P = BPP.
Then we know there exist pseudorandom number generators vs P.
Suppose the adversary is NP.
Now, any pseudorandom number generator that only uses P will fail. (Since NP can invert ...
- 77
3
votes
1
answer
357
views
Mathematical Programming with other Algebras than Linear
Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization.
What analogies are there for ...
- 2,383
2
votes
0
answers
120
views
Circuits by Level
Context: googling existing results on Circuit Complexity.
I'm aware there are classes like AC, ACC, TC, NC, etc..
Now, suppose I have a circuit, it has the following additional program:
The circuit ...
- 77
8
votes
2
answers
2k
views
Turing machines that always halt
Needed for this paper:
Here is a possibly more clear version of my question. A Turing machine (with $1$ tape) has sets of tape letters $Y$, state letters $Q$, two symbols $\alpha$ and $\omega$ that ...
user6976
2
votes
1
answer
471
views
Tail Bound on Binomial
Context: circuit complexity argument:
How do I show that $$\sum_{i=0}^{n/2- \sqrt{n}} {n \choose i} \geq 2^n/50$$ ? (as n goes to infinity)
[This shows up in proving Mod2 is not in ACC(3)].
...
- 29
1
vote
2
answers
289
views
Pseudorandom Functions / Pseudorandom Permutations
I'm reading Yao's unpredictability -> pseudorandomness construction
and Goldreich/levin's pseudorandom permutation -> pseudorandom generator construction.
My question is:
is there a direct way to ...
- 13
5
votes
3
answers
8k
views
Linear programming - uniqueness of optimal solution
Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution?
My general problem is to get any vertex of a polytope formed by a ...
- 85
3
votes
2
answers
881
views
Formal verification in complexity theory
Reading books and papers on complexity theory, I am struck by the extreme degree to which proofs are stated in an intuitive, hand-wavy way. The alternative is to give a lot of details about the coding ...
- 3,475
3
votes
2
answers
439
views
Has Oracles actually provided intuition for proving anything in Complexity Theory?
[EDIT: I realize this question is soft. I realize some people want to close this question. The goal here is trying to answer the following question:
So I see these research papers that provide papers ...
- 61
3
votes
1
answer
1k
views
Open?: Bpp VS EXP^NP
Known:
BPP vs NEXP is open.
BPP is strict subset of EXP^EXP.
Question:
Is BPP vs EXP^NP open?
If so, is there any class between EXP^NP, EXP^EXP concerning which vs BPP it's still open?
Thanks!
...
- 61
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
10
votes
1
answer
734
views
Polynomial-time complexity and a question and a remark of Serre
My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...
- 26k
3
votes
1
answer
225
views
Oracle Separation Results: A^O != B^O yet A = B ?
I know that there exists classes $A$ and $B$ such that:
$A^{O_1} = B^{O_1}$, $A^{O_2} != B^{O_2}$.
Now, this is my question: do we know of any classes $A$ and $B$ such that $A=B$, yet
there is an ...
- 31
2
votes
0
answers
215
views
Number of breakpoints in parametric maximum flow problems
The parametric maximum flow problem can be formulated as
$$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),
$$
where all $c_{ij}<0$ (so that ...
- 567
14
votes
3
answers
3k
views
Definition of relativization of complexity class
Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?
Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
- 3,475
1
vote
0
answers
228
views
Inherent complexity of a language --- when does it exist?
For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ ...
- 3,475
2
votes
2
answers
390
views
Oracle Separation Survey
Is there a survey (or a website) somewhere that lists all known separation results?
I.e. it has a list of triples:
$$ (C_1, C_2, A)$$
where
...
- 21
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
7
votes
2
answers
5k
views
the complexity of Lanczos method
Hi, all
I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of ...
- 73
4
votes
1
answer
259
views
Survey on Structural Complexity
Alot of the proofs I've been recently reading:
IP / PSpace / MIP / NEXP / randomized reductions
have a certain flavour involving proofs showing equivalence/relation between various complexity ...
