Reference-request is used when the author needs to know about work related to the question.

learn more… | top users | synonyms

4
votes
2answers
158 views

Decision version of matrix multiplication problem

Is there any known decision version of matrix multiplication problem such that the time complexity of the best known algorithm for this decision problem is $O(n^k)$ for $n \times n$-dimensional ...
7
votes
1answer
405 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
11
votes
1answer
112 views

Algebraically Compact Categories

I read Freyd's paper "Algebraically Complete Categories" in the famous Como90 and I have two questions about the notion of algebraic compactness he defined in that paper. (If you are not familiar with ...
10
votes
2answers
157 views

W[1]-hard problems on bounded degree graphs

Do you know problems which are W[1]-hard even for bounded degree graphs? Metric Dimension is hard on graphs with degree at most 3, but it is W[2]-hard. Red-Blue Nonblocker used to be W[1]-hard on ...
5
votes
0answers
100 views

Lower bound for the maximal vectors problem

I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
0
votes
1answer
59 views

Is there an efficient construction for a trilinear pairing that has been used in theory or practice

A trilinear pairing is defined a function $e:G_1^3 \rightarrow G_2$, such that it satisfies the property $e(k_1^a, k_2^b, k_3^c) = e(k_1,k_2,k_3)^{abc}$ In general I am trying to solve the following ...
1
vote
1answer
101 views

Good resources to learn loopy belief propagation

What are some of the good references to understand loopy belief propagation and the need for it? I am looking for both theory and applications (for instance in coding/information and learning theory). ...
1
vote
0answers
57 views

looking for notable applications of ASP (Answer Set Programming) in TCS

a recent difficult question of interest to the group[1] by GB has possibly led to verification of a new graph property by dspyz, by use of Answer Set Programming/ASP. via sophisticated logic ...
3
votes
0answers
68 views

Minimize the time when guard observes more than one event (for fixed number of guards)

Consider the following optimization problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which ...
20
votes
4answers
987 views

Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. ...
-3
votes
1answer
118 views

“tree-like” vs “DAG-like” resolution

hi all there seems to be a deep/not-much-explored phenomenon in the way that SAT resolution proofs can define a tree and/or a DAG & its relationship to lower bounds/circuit complexity. could there ...
8
votes
0answers
78 views

Depth of bounded fan-in circuits for unbounded fan-in circuits

Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$. What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size ...
3
votes
0answers
310 views

What's the hardest problem with a non-trivial exact algorithm?

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough. I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
12
votes
1answer
717 views

Complexity class of this problem?

I am trying to understand to which complexity class the following problem belongs: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
2
votes
0answers
60 views

WFSA over hyperreals

Are there any works where authors tried to define weighted finite state automata over hyperreals (or a similar object allowing for infinite and infinitesimal values) in an attempt to make automata ...
2
votes
1answer
108 views

Complexity of determining unique elements of each cycle in a permutation

It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation. But suppose that we know ...
2
votes
0answers
86 views

Computing spanning trees with low crossing number using simplicial partitions

I'm reading a paper that uses the following result: Let $S$ be a set of $n$ points in the plane. Then a spanning tree for $S$ with crossing number $O(\sqrt{n})$ can be computed in ...
3
votes
0answers
52 views

Randomized Parallel Algorithm for Maximal Independent Set

There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...
1
vote
1answer
109 views

Hardness of XSAT

The standard NP-hard SAT problem is the problem of Boolean satisfiability of conjunctions of clauses, where clauses are disjunctions of literals. I am interested in the problem of the Boolean ...
0
votes
0answers
31 views

Reference Request: Surveys on attacks on security schemes

I am new to provable security and am working on cryptanalysis of a certificate free signature scheme. Unfortunately, I don't have much knowledge about finding attacks on schemes. It would be very ...
4
votes
0answers
73 views

Variant of Toda's theorem for intermediate levels of the polynomial hierarchy

Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states: Let $\# wSAT$ be the number of ...
5
votes
1answer
89 views

Inverse of transducer compositions

Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM transducer). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written ...
3
votes
0answers
78 views

Gradual increase in hardness from P to PH of #SAT

We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem. However, counting the number of solutions to ...
2
votes
0answers
56 views

Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...
15
votes
0answers
246 views

Is cubic complexity still the state of the art for LP?

According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ ...
1
vote
1answer
68 views

Reference for Dudley's chaining integral

Dudley's chaining integral is commonly used to bound Rademacher complexities. I recall seeing several papers give this as the reference ...
5
votes
0answers
78 views

Branching Boosting Algorithms

Long/Servedio showed AdaBoost/etc doesn't perform well under noisy environments, but that branching forms of boosting do. Can any point me to a list of branching boosting algorithms, or a reference ...
3
votes
2answers
131 views

The length of non perfect binary 1 error correcting codes

I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other ...
1
vote
0answers
38 views

Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (*scanned) in its entirety. The Gang of Six algorithm ...
7
votes
3answers
338 views

Can one automate algorithmic analysis?

Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a ...
1
vote
1answer
196 views

finding “hubs” in a graph

consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ ...
7
votes
1answer
192 views

Reference for Turing to many-one reductions

I am looking for a reference on `reducing' Turing reductions to many-one reductions. I have in mind a statement of the following form (similar enough statements would also satisfy me): Theorem. If ...
1
vote
2answers
192 views

Foundational textbook(s) for Complexity and Computability on Real Numbers

It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ...
4
votes
1answer
259 views

Computing the convex hull of lattice points

Consider a set of $n$ points in $\mathbb Z^2$. It is known that their convex hull can be computed in time $O(n\log n)$, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These ...
0
votes
0answers
58 views

grammar compression/induction in proofs

are there (interesting/notable) cases of grammar compression and/or grammar induction used in TCS proofs or analysis? this question is somewhat related to [1]. [1] techniques or examples of ...
4
votes
0answers
215 views

Heuristic algorithm design techniques

I am looking for a good relatively complete and up-to-date book or survey about heuristic algorithm design techniques.
2
votes
1answer
155 views

Dividing users with certain files into 2 equal groups

I am framing a particular combinatorial question using users and files for better understanding. Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, ...
3
votes
1answer
82 views

Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

In the quantum adiabatic algorithm, one prepares the ground state of a Hamiltonian $H_{i}$, and then evolves the Hamiltonian slowly over time to a target Hamiltonian $H_{f}$ via the interpolation ...
2
votes
1answer
106 views

Learning road map for functional programming from the viewpoint of category theory

I am now considering about studying functional programming from the viewpoint of category theory. There are a lot of books about functional programming and category theory, I want some suggestions ...
18
votes
3answers
835 views

NP complete graph problems about structural properties

(This question is a bit of a "survey".) I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural ...
4
votes
0answers
133 views

The weakly NP-complete problems and their associated counting problem

Are there weakly NP-complete problems whose associated counting problem can be computed in pseudo-polynomial time? And if one were to be found (and assuming it is #P-complete), what would be the ...
6
votes
1answer
352 views

Linear diophantine equation in non-negative integers

There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative ...
3
votes
2answers
232 views

Symbolic Execution is a case of Abstract Interpretation?

This is written in the wiki entry of Symbolic Execution, but I can't find any reference for it. Can anyone show me a pointer? Thank you.
8
votes
1answer
233 views

Finding even cycle in directed graphs

Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by YUSTER and ZWICK states that the problem is not known to be in $P$ nor is it known to ...
6
votes
2answers
168 views

FPT algorithm for Partial k-tree Isomorphism

H.L. Bodlander in Polynomial algorithms for graph isomorphism and chromatic index on partial $k$-trees given a polynomial time algorithm for graph isomorphism when $k$ is constant. Is there any FPT ...
4
votes
1answer
153 views

Is bounded-error probabilistic computation sensitive to transition types?

In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in ...
2
votes
0answers
90 views

Geometry on a space of polynomial functions

I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references. Let $P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow ...
11
votes
7answers
613 views

Handbook of advanced algorithms

I am looking for resources (preferably a handbook) on advanced topics in algorithms (topics beyond what is covered in algorithms textbooks like CLRS and DPV). The type of material that can be used ...
11
votes
0answers
148 views

Name and references for balanced variant of the long code?

The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one ...
5
votes
0answers
151 views

Lemma about intersecting sets

I use the following Lemma and I wonder whether it is known in literature. If you look at the proof it feels like it should be known from combinatorics or extremal graph theory. Lemma. Let $A$ be an ...