Questions tagged [reference-request]

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

29
votes
2answers
838 views

Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
6
votes
1answer
210 views

Ensemble of tree decompositions for all-pairs problem

Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of self avoiding walks on $G$ passing through nodes $u$ and $v$ for all pairs of nodes $(u,v)$. For a single pair $(...
22
votes
2answers
792 views

Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?

I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
33
votes
3answers
2k views

complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
20
votes
3answers
1k views

Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
3
votes
4answers
969 views

Algorithm for finding similar images

If you go to FFFFOUND! and click on some image you will notice that on the new page, under the image, there is a section called "You may like these images." which suggests 10 images that look similar ...
41
votes
6answers
2k views

Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
7
votes
1answer
1k views

Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the ...
16
votes
1answer
672 views

Reference for (odd-hole,antihole)-free graphs?

X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
17
votes
1answer
445 views

The structure of pathological instances for simplex algorithms

As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum....
3
votes
0answers
191 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
13
votes
2answers
241 views

complexity of randomized gossiping

The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes. Now, my question is in the ...
13
votes
2answers
1k views

Difference lists in functional programming

The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), ...
13
votes
3answers
746 views

Is the 3-sphere recognition problem NP-complete?

It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere is in NP, via work by Saul Schleimer in 2004: "Sphere recognition lies in NP" arXiv:math/0407047v1 [math.GT]. ...
27
votes
1answer
803 views

Other applications of Karger-Stein branching amplification?

I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don'...
20
votes
1answer
458 views

Are there efficient general Bonferroni-style bounds known?

A classic problem in probability theory is to express the probability of an event in terms of more specific events. In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$. Let's ...
7
votes
0answers
2k views

Fast Hamiltonian Cycle finding Algorithm

We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there ...
13
votes
1answer
520 views

Reference Request: Submodular Minimization and Monotone Boolean Functions

Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, ...
17
votes
3answers
598 views

Formal representation of rings in computations

While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not ...
11
votes
1answer
375 views

Agnostic learning over arbitrary distributions

Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:...
12
votes
7answers
978 views

Interdisciplinary topics between control theory and theoretical computer science

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, ...
8
votes
2answers
735 views

Techniques for proving bounds on integrality gap in LP(SDP)

A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a ...
10
votes
3answers
554 views

Papers on fault handling in distributed systems

What papers on handling errors in distributed systems do you recommend?
33
votes
11answers
22k views

Books on automata theory for self-study

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
74
votes
20answers
8k views

Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?

Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those ...
-1
votes
1answer
372 views

What are the applications of scene recognition algorithms? [closed]

One common application is for use with automatic mode cameras. They can recognize the scene categories and then adjust the camera parameters to take the best shot of the scene. I am wondering what ...
4
votes
1answer
632 views

Offline multidimensional RMQ/RSQ in query model

Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ) you are given a $d$-dimensional array with $n$ elements, and given a $d$-dimensional box, you wish to determine the max/...
28
votes
6answers
2k views

Alternative proofs of Schwartz–Zippel lemma

I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz. Are there any other ...
2
votes
0answers
533 views

State of the art for SAT solvers [duplicate]

Possible Duplicate: Best Upper Bounds on SAT I'm working on the obstruction-set-free grid coloring problem; a specific instance of it is described in this previous question on coloring 17x17 ...
13
votes
4answers
740 views

Reference for fundamental theorem on tree rotations

Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental: Let A and B be binary ...
557
votes
6answers
114k views

What's new in purely functional data structures since Okasaki?

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by ...
6
votes
3answers
497 views

Best sources on data stream algorithms

I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone. I'd be thus grateful for pointers to really good sources on the topic, ...
39
votes
7answers
4k views

Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
11
votes
1answer
399 views

Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...
22
votes
6answers
2k views

Introduction to spectral graph theory

What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
9
votes
1answer
307 views

Metric graph theory database search algorithms

I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News. One chapter discusses current software implementations, and the database searches (and other ...
11
votes
1answer
386 views

Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
20
votes
3answers
638 views

Is it hard to find optimal addition chains?

An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the ...
5
votes
3answers
388 views

Reference for the shortcomings of Google's PageRank algorithm?

Sometimes, when using Google search, you don't immediately get quality results to your query. It is seems that PageRank algorithm gets distracted by widely used keywords that have different meanings ...
8
votes
3answers
2k views

Reference Request: Application of Block Designs to Software Testing

I've started looking at incidence structures and combinatorial designs (possible motivation: to upper-bound some structures in generalized self-assembly), and the Wikipedia article makes the following ...
11
votes
2answers
422 views

Does the System F with pairs have the strong normalisation and subject reduction properties?

It is easy to look in a lot of textbooks the proofs of subject reduction and strong normalisation for System F, also, sometimes there are definitions of System F with pairs, where (t,r) is a term, not ...
16
votes
2answers
919 views

A reading list on experimental algorithmics

As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA. Which were the foundational works? What are the main results? How are they characterized? Any interesting connections ...
5
votes
0answers
604 views

Learning quantum CS [duplicate]

Possible Duplicate: What is the quantum computational model? What is the best way to study quantum branch of CS for the person with rather advanced background in classical CS? Does one need to ...
45
votes
4answers
3k views

Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
5
votes
2answers
912 views

Handbook of Logic in Computer Science - is it worth it?

I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to ...
15
votes
1answer
349 views

Triangulating a Planar Polygon

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
18
votes
1answer
1k views

Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
19
votes
3answers
834 views

What algorithms are known for computing Craig interpolants?

Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the ...
35
votes
1answer
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
2
votes
3answers
924 views

Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

optimization problem Input: cubic Hamiltonian graph feasible solution: A simple path measure to optimize: length of the simple path Design a polynomial-time algorithm that outputs the longest path ...