94 citations
- Cornell UniversityUS2 papers
- Courant Institute of Mathematical SciencesUS2 papers
- University of California, DavisUS2 papers
- University of Illinois Urbana-ChampaignUS2 papers
- Amsterdam University of the ArtsNL1 paper
- Harvard University PressUS1 paper
- Hebrew University of JerusalemIL1 paper
- IIT@MITUS1 paper
- Large Synoptic Survey Telescope CorporationUS1 paper
- Lowell ObservatoryUS1 paper
- Massachusetts Institute of TechnologyUS1 paper
- Microsoft Research (India)IN1 paper
Showing 2008 · cs.CCShow all
3 papers · 2 filters
cs.CC2008★ 22 cited
A Dual Polynomial for OR
Robert Spalek
We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynom…
cs.CC2008
General Algorithms for Testing the Ambiguity of Finite Automata
Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with -transitions. It gives an algorithm for testing th…
cs.CC2008
3-Way Composition of Weighted Finite-State Transducers
Cyril Allauzen, Mehryar Mohri
Composition of weighted transducers is a fundamental algorithm used in many applications, including for computing complex edit-distances between automata, or string kernels in mach…