Skip to main content

All Questions

Filter by
Sorted by
Tagged with
5 votes
1 answer
2k views

Non-uniform complexity of the halting problem

This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: https://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem What can be said ...
Vanessa's user avatar
  • 1,368
5 votes
2 answers
457 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
Andrew's user avatar
  • 341
5 votes
1 answer
465 views

Computational complexity of proof verification

Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...
jg1896's user avatar
  • 3,318
5 votes
1 answer
502 views

Time Complexity of the Word Problem for Finite Permutation Groups

Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the ...
StefanH's user avatar
  • 798
5 votes
2 answers
4k views

sparsity of QR decomposition

Hi, everyone! I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
Mike's user avatar
  • 51
5 votes
1 answer
2k views

BPP being equal to #P under Oracle

Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle. In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{...
Opt's user avatar
  • 601
5 votes
2 answers
3k views

symmetric difference of languages - both are in NP and coNP

I have this problem, Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like: $L_1 \oplus L_2$ = {x | x is in exactly one of $...
Stefan.M's user avatar
  • 153
5 votes
2 answers
2k views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
thinkbear's user avatar
  • 211
5 votes
2 answers
3k views

Continuous Linear Programming: Estimating a Solution

I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...
David S-D's user avatar
  • 373
5 votes
1 answer
461 views

Discrete log problem modified

Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log_g a < \log_g b$? (Here we ...
Craig Feinstein's user avatar
5 votes
3 answers
1k views

Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions? This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
Joseph Soulbringer's user avatar
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 ...
Miroslav Korbelar's user avatar
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 ...
Michael's user avatar
  • 85
5 votes
2 answers
413 views

An interesting variant on the maximum independent set problem.

Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex ...
Iltl's user avatar
  • 213
5 votes
1 answer
226 views

Complexity of counting MAXCUT in planar graphs -- seemingly contradicting claims

Confusion is likely. Appears to me two papers give contradicting claims about the complexity of counting MAXCUT in planar graphs. Exact Max 2-SAT: Easier and Faster p. 6 However, counting the ...
joro's user avatar
  • 25.4k
5 votes
1 answer
220 views

What is the (mixed strategies) equilibrium of this game?

Given a weight vector $w\in [0,1]^d$ such that $\sum w_i=1$, the game goes as follows: Two players, $X,Y$ choose strategies $x,y\in [0,1]^d$ such that $\sum x_i = \sum y_i = 1$. The utility (profit) ...
R B's user avatar
  • 618
5 votes
1 answer
2k views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
Turbo's user avatar
  • 13.9k
5 votes
1 answer
902 views

How much of P versus NP's difficulty stems from having to rule out the existence of Turing machines that "accidentally" solve, say, 3-SAT efficiently?

It seems like there is a sense in which a Turing machine that demonstrates P=NP could be said to "accidentally" exist. I'm wondering the extent to which the possibility of such machines is the main ...
Chris Jerdonek's user avatar
5 votes
1 answer
264 views

What oracles make finding isomorphism (of finite structures) easy?

Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer ...
Noah Schweber's user avatar
5 votes
1 answer
265 views

Approximation of Hamiltonian cycles

Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
Beduin's user avatar
  • 53
5 votes
1 answer
175 views

Computational complexity of deciding if two elements are in the same cycle of a permutation

Given $n\in \mathbb{N}$, we have a bijection $P:\{0,1\}^n\to\{0,1\}^n$, i.e. $P$ is a permutation of $2^n$ symbols, $P\in S_{2^n}$. The permutation $P$ can be calculated efficiently, i.e. by a ...
Doriano Brogioli's user avatar
5 votes
1 answer
276 views

NP-hardness of a sequence problem

Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
lchen's user avatar
  • 367
5 votes
1 answer
354 views

Fastest deterministic factoring algorithm in subexponential space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-...
Dan Brumleve's user avatar
  • 2,302
5 votes
1 answer
453 views

an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
Alexey Milovanov's user avatar
5 votes
1 answer
488 views

Division by $n$ in elliptic curves

Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let $N=\#E(\...
Meysam Ghahramani's user avatar
5 votes
1 answer
384 views

Examples of Polyhedra with Large Shadows

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
Christopher's user avatar
5 votes
2 answers
604 views

Sets of vectors related by a rotation

We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$. The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ ...
Piotr Migdal's user avatar
  • 1,612
5 votes
1 answer
269 views

Simplices in convex polytopes

This question is a direct generalization of: Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices Given a convex ...
Igor Rivin's user avatar
  • 96.4k
5 votes
2 answers
371 views

What is the fastest way of finding a complement?

I am given a direct factor $N$ which is a normal subgroup of a group $G$. I want to find a complement of $N$ in $G$. The model of computation is RAM. It takes $O(n)$ time to find an inverse of one ...
old's user avatar
  • 159
5 votes
1 answer
178 views

Degree $d$ function with boolean inputs with small range is a junta?

Let $f : \{-1,1\}^n \rightarrow \{-1,1\}$ be a boolean function which is of degree at most $d$ when expressed as a multilinear polynomial ($f(x) = \sum_S \hat{f}(S) \prod_{i \in S} x_i$). It is known ...
user101129's user avatar
5 votes
1 answer
183 views

Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity? Especially modeling ...
Manfred Weis's user avatar
  • 13.2k
5 votes
1 answer
245 views

What is Known About the Complexity of Calculating Minimal Surface Polyhedra?

I am currently ruminating about ways of generalizing Minimum Spanning Trees to Minimum Spanning "Hypertrees", where the cost is associated with simplex volumes and, where certain topological ...
Manfred Weis's user avatar
  • 13.2k
5 votes
1 answer
644 views

The existential theory of the reals

Some definitions of the existential theory of the reals (ETR) allow a real closed field and some definitions allow only rational numbers as coefficients of polynomials. Which one is correct? Will the ...
dschaehi's user avatar
5 votes
2 answers
2k views

Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
user3645's user avatar
  • 191
5 votes
2 answers
612 views

A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
Alexander S. Kulikov's user avatar
5 votes
2 answers
1k views

Applications of minmax theorem(s)

Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions, $$ \inf_Y \sup_X f = \sup_X \...
5 votes
1 answer
123 views

Algorithms to factorize words into product of powers

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references. Let $A$ be a finite set of symbols, are there ...
rtsss's user avatar
  • 477
5 votes
1 answer
345 views

Decoding a Remark of Gödel on Complexity Theory

In Gödel's Collected Works (Vol 2), there is a discussion of von Neumann which was brought about by a query, made to Gödel, concerning the existence of a Turing machine which is so complex that its ...
cmn1's user avatar
  • 314
5 votes
1 answer
213 views

Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
user40780's user avatar
  • 867
5 votes
2 answers
450 views

A simple language and systematic computations

The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact history)....
Włodzimierz Holsztyński's user avatar
5 votes
1 answer
475 views

Maximal chain of 1s in binary strings

Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$ Of ...
Knot's user avatar
  • 325
5 votes
2 answers
584 views

Continuous Transportation Problem

Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
Carrie Nuttall's user avatar
5 votes
1 answer
214 views

Graphs with Hermitian Unitary Edge Weights

Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is Huang's preprint, a discussion on Scott ...
5 votes
1 answer
394 views

Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
Max Hopkins's user avatar
5 votes
1 answer
148 views

Elliptic curves: for $P = aG$ for some $a$, what is $Q = a^{-1}G$?

Given an elliptic curve group with a generator $G$ where $G$ has a prime order, p. Given a point $P=aG$ for some unknown $a$. Is it possible to efficiently calculate $Q=a^{-1}G$ without a discrete ...
Rupsbant's user avatar
5 votes
3 answers
422 views

Request for reference for some proofs about Gowers' norm

For any map $f : \mathbb{F}_2^n \rightarrow \mathbb{C}$ we define its $d^{th}-$Gowers' Norm (for $1 \leq d \leq n$) as, $\|f\|_{U^d(\mathbb{F}_2^n)}^{2^d} = \mathbb{E}_{L : \mathbb{F}_2^d \rightarrow \...
gradstudent's user avatar
  • 2,246
5 votes
1 answer
523 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
dhasson's user avatar
  • 183
5 votes
1 answer
2k views

Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?" More formally and generally, what I'm looking for ...
Xoph's user avatar
  • 153
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 ...
Igor Rivin's user avatar
  • 96.4k
5 votes
1 answer
271 views

Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
Vinayak Pathak's user avatar

1
9 10
11
12 13
37