focs93.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>34. FOCS 1993: Palo Alto, California</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head><body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>34. <a href="index.html">FOCS</a> 1993: Palo Alto, California</h1> 34th Annual Symposium on Foundations of Computer Science, Palo Alto California, 3-5 November 1993. IEEE Computer Society <ul> <li><a name="BlumC93" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/c/Chalasani:Prasad.html">Prasad Chalasani</a>: An On-Line Algorithm for Improving Performance in Navigation. 2-11 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumC93">BibTeX</a></font> <li><a name="IraniR93" href="../../indices/a-tree/i/Irani:Sandy.html">Sandy Irani</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>: On the Value of Information in Coordination Games (preliminary version). 12-21 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/IraniR93">BibTeX</a></font> <li><a name="AwerbuchBF93" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>: Heat & Dump: Competitive Distributed Paging. 22-31 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchBF93">BibTeX</a></font> <li><a name="AwerbuchAP93" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>: Throughput-Competitive On-Line Routing. 32-40 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchAP93">BibTeX</a></font> <li><a name="Gottlob93" href="../../indices/a-tree/g/Gottlob:Georg.html">Georg Gottlob</a>: NP Trees and Carnap's Modal Logic. 42-51 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gottlob93">BibTeX</a></font> <li><a name="Cosmadakis93" href="../../indices/a-tree/c/Cosmadakis:Stavros_S=.html">Stavros S. Cosmadakis</a>: Logical Reducibility and Monadic NP. 52-61 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cosmadakis93">BibTeX</a></font> <li><a name="GuptaP93" href="../../indices/a-tree/g/Gupta:Vineet.html">Vineet Gupta</a>, <a href="../../indices/a-tree/p/Pratt:Vaughan_R=.html">Vaughan R. Pratt</a>: Gages Accept Concurrent Behavior. 62-71 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaP93">BibTeX</a></font> <li><a name="CloteIK93" href="../../indices/a-tree/c/Clote:Peter.html">Peter Clote</a>, <a href="../../indices/a-tree/i/Ignjatovic:Aleksandar.html">Aleksandar Ignjatovic</a>, <a href="../../indices/a-tree/k/Kapron:Bruce_M=.html">Bruce M. Kapron</a>: Parallel computable higher type functionals (Extended Abstract). 72-81 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CloteIK93">BibTeX</a></font> <li><a name="Karger93" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>: Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees. 84-93 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Karger93">BibTeX</a></font> <li><a name="JerrumS93" href="../../indices/a-tree/j/Jerrum:Mark.html">Mark Jerrum</a>, <a href="../../indices/a-tree/s/Sorkin:Gregory_B=.html">Gregory B. Sorkin</a>: Simulated Annealing for Graph Bisection. 94-103 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JerrumS93">BibTeX</a></font> <li><a name="ChenR93" href="../../indices/a-tree/c/Chen:Shenfeng.html">Shenfeng Chen</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs. 104-112 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChenR93">BibTeX</a></font> <li><a name="Hastad93" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: The shrinkage exponent is 2. 114-123 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Hastad93">BibTeX</a></font> <li><a name="HastadJP93" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/j/Jukna:Stasys.html">Stasys Jukna</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>: Top-Down Lower Bounds for Depth 3 Circuits. 124-129 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HastadJP93">BibTeX</a></font> <li><a name="Smolensky93" href="../../indices/a-tree/s/Smolensky:Roman.html">Roman Smolensky</a>: On Representations by Low-Degree Polynomials. 130-138 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Smolensky93">BibTeX</a></font> <li><a name="AgarwalaF93" href="../../indices/a-tree/a/Agarwala:Richa.html">Richa Agarwala</a>, <a href="../../indices/a-tree/f/Fern=aacute=ndez=Baca:David.html">David Fernández-Baca</a>: A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed. 140-147 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AgarwalaF93">BibTeX</a></font> <li><a name="BafnaP93" href="../../indices/a-tree/b/Bafna:Vineet.html">Vineet Bafna</a>, <a href="../../indices/a-tree/p/Pevzner:Pavel_A=.html">Pavel A. Pevzner</a>: Genome Rearrangements and Sorting by Reversals. 148-157 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BafnaP93">BibTeX</a></font> <li><a name="TengY93" href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>, <a href="../../indices/a-tree/y/Yao:F=_Frances.html">F. Frances Yao</a>: Approximating Shortest Superstrings. 158-165 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/TengY93">BibTeX</a></font> <li><a name="RazS93" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/s/Spieker:Boris.html">Boris Spieker</a>: On the ``log rank''-Conjecture in Communication Complexity. 168-176 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazS93">BibTeX</a></font> <li><a name="JuedesL93" href="../../indices/a-tree/j/Juedes:David_W=.html">David W. Juedes</a>, <a href="../../indices/a-tree/l/Lutz:Jack_H=.html">Jack H. Lutz</a>: The Complexity and Distribution of Hard Problems (Extended Abstract). 177-185 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JuedesL93">BibTeX</a></font> <li><a name="Chaudhuri93" href="../../indices/a-tree/c/Chaudhuri:Shiva.html">Shiva Chaudhuri</a>: Sensitive Functions and Approximate Problems. 186-193 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chaudhuri93">BibTeX</a></font> <li><a name="AfekS93" href="../../indices/a-tree/a/Afek:Yehuda.html">Yehuda Afek</a>, <a href="../../indices/a-tree/s/Stupp:Gideon.html">Gideon Stupp</a>: Synchronization power depends on the register size (Preliminary Version). 196-205 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AfekS93">BibTeX</a></font> <li><a name="ChaudhuriHLT93" href="../../indices/a-tree/c/Chaudhuri:Soma.html">Soma Chaudhuri</a>, <a href="../../indices/a-tree/h/Herlihy:Maurice.html">Maurice Herlihy</a>, <a href="../../indices/a-tree/l/Lynch:Nancy_A=.html">Nancy A. Lynch</a>, <a href="../../indices/a-tree/t/Tuttle:Mark_R=.html">Mark R. Tuttle</a>: A Tight Lower Bound for k-Set Agreement. 206-215 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChaudhuriHLT93">BibTeX</a></font> <li><a name="Poon93" href="../../indices/a-tree/p/Poon:C=_K=.html">C. K. Poon</a>: Space Bounds for Graph Connectivity Problems on Node-named JAGs and Node-ordered JAGs. 218-227 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Poon93">BibTeX</a></font> <li><a name="BarnesE93" href="../../indices/a-tree/b/Barnes:Greg.html">Greg Barnes</a>, <a href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>: Time-Space Bounds for Directed s-t Connectivity on JAG Models (Extended Abstract). 228-237 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarnesE93">BibTeX</a></font> <li><a name="Feige93" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>: A Randomized Time-Space Tradefoff of \tildeO(m\tildeR) for USTCON. 238-246 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Feige93">BibTeX</a></font> <li><a name="ColeCGGHMPR93" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/c/Crochemore:Maxime.html">Maxime Crochemore</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/g/Gasieniec:Leszek.html">Leszek Gasieniec</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>, <a href="../../indices/a-tree/p/Park:Kunsoo.html">Kunsoo Park</a>, <a href="../../indices/a-tree/r/Rytter:Wojciech.html">Wojciech Rytter</a>: Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. 248-258 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ColeCGGHMPR93">BibTeX</a></font> <li><a name="KleinS93" href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>, <a href="../../indices/a-tree/s/Subramanian:Sairam.html">Sairam Subramanian</a>: A linear-processor polylog-time algorithm for shortest paths in planar graphs. 259-270 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinS93">BibTeX</a></font> <li><a name="AumannKPR93" href="../../indices/a-tree/a/Aumann:Yonatan.html">Yonatan Aumann</a>, <a href="../../indices/a-tree/k/Kedem:Zvi_M=.html">Zvi M. Kedem</a>, <a href="../../indices/a-tree/p/Palem:Krishna_V=.html">Krishna V. Palem</a>, <a href="../../indices/a-tree/r/Rabin:Michael_O=.html">Michael O. Rabin</a>: Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs. 271-280 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AumannKPR93">BibTeX</a></font> <li><a name="AslamD93" href="../../indices/a-tree/a/Aslam:Javed_A=.html">Javed A. Aslam</a>, <a href="../../indices/a-tree/d/Decatur:Scott_E=.html">Scott E. Decatur</a>: General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Bounding. 282-291 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AslamD93">BibTeX</a></font> <li><a name="AlonBCH93" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/b/Ben=David:Shai.html">Shai Ben-David</a>, <a href="../../indices/a-tree/c/Cesa=Bianchi:Nicol=ograve=.html">Nicolò Cesa-Bianchi</a>, <a href="../../indices/a-tree/h/Haussler:David.html">David Haussler</a>: Scale-sensitive Dimensions, Uniform Convergence, and Learnability. 292-301 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonBCH93">BibTeX</a></font> <li><a name="Bshouty93" href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>: Exact Learning via the Monotone Theory (Extended Abstract). 302-311 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Bshouty93">BibTeX</a></font> <li><a name="BlumK93" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>: Learning an Intersection of k Halfspaces over a Uniform Distribution. 312-320 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumK93">BibTeX</a></font> <li><a name="RajagopalanV93" href="../../indices/a-tree/r/Rajagopalan:Sridhar.html">Sridhar Rajagopalan</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs. 322-331 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RajagopalanV93">BibTeX</a></font> <li><a name="Callahan93" href="../../indices/a-tree/c/Callahan:Paul_B=.html">Paul B. Callahan</a>: Optimal Parallel All-Nearest-Neighbors Using the Well-Separated Pair Decomposition (Preliminary Version). 332-340 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Callahan93">BibTeX</a></font> <li><a name="KaklamanisKR93" href="../../indices/a-tree/k/Kaklamanis:Christos.html">Christos Kaklamanis</a>, <a href="../../indices/a-tree/k/Krizanc:Danny.html">Danny Krizanc</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: Universal Emulations with Sublogarithmic Slowdown. 341-350 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaklamanisKR93">BibTeX</a></font> <li><a name="Yao93" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Quantum Circuit Complexity. 352-361 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yao93">BibTeX</a></font> <li><a name="BrassardCJL93" href="../../indices/a-tree/b/Brassard:Gilles.html">Gilles Brassard</a>, <a href="../../indices/a-tree/c/Cr=eacute=peau:Claude.html">Claude Crépeau</a>, <a href="../../indices/a-tree/j/Jozsa:Richard.html">Richard Jozsa</a>, <a href="../../indices/a-tree/l/Langlois:Denis.html">Denis Langlois</a>: A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties. 362-371 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BrassardCJL93">BibTeX</a></font> <li><a name="GilleronTT93" href="../../indices/a-tree/g/Gilleron:R=eacute=mi.html">Rémi Gilleron</a>, <a href="../../indices/a-tree/t/Tison:Sophie.html">Sophie Tison</a>, <a href="../../indices/a-tree/t/Tommasi:Marc.html">Marc Tommasi</a>: Solving Systems of Set Constraints with Negated Subset Relationships. 372-380 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GilleronTT93">BibTeX</a></font> <li><a name="HalperinS93" href="../../indices/a-tree/h/Halperin:Dan.html">Dan Halperin</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment. 382-391 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HalperinS93">BibTeX</a></font> <li><a name="Chazelle93" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: Geometric Discrepancy Revisited. 392-399 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle93">BibTeX</a></font> <li><a name="BronnimannCM93" href="../../indices/a-tree/b/Br=ouml=nnimann:Herv=eacute=.html">Hervé Brönnimann</a>, <a href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>, <a href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>: Product Range Spaces, Sensitive Sampling, and Derandomization. 400-409 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BronnimannCM93">BibTeX</a></font> <li><a name="Egidi93" href="../../indices/a-tree/e/Egidi:Lavinia.html">Lavinia Egidi</a>: The Complexity of the Theory of p-adic Numbers. 412-421 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Egidi93">BibTeX</a></font> <li><a name="Ge93" href="../../indices/a-tree/g/Ge:Guoqiang.html">Guoqiang Ge</a>: Testing Equalities of Multiplicative Representations in Polynomial Time (Extended Abstract). 422-426 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ge93">BibTeX</a></font> <li><a name="BealsB93" href="../../indices/a-tree/b/Beals:Robert.html">Robert Beals</a>, <a href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>: Las Vegas algorithms for matrix groups. 427-436 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BealsB93">BibTeX</a></font> <li><a name="Radzik93" href="../../indices/a-tree/r/Radzik:Tomasz.html">Tomasz Radzik</a>: Faster Algorithms for the Generalized Network Flow Problem. 438-448 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Radzik93">BibTeX</a></font> <li><a name="Gabow93" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>: A Framework for Cost-scaling Algorithms for Submodular Flow Problems. 449-458 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gabow93">BibTeX</a></font> <li><a name="AwerbuchL93" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>: A Simple Local-Control Approximation Algorithm for Multicommodity Flow. 459-468 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchL93">BibTeX</a></font> <li><a name="FrandsenMS93" href="../../indices/a-tree/f/Frandsen:Gudmund_Skovbjerg.html">Gudmund Skovbjerg Frandsen</a>, <a href="../../indices/a-tree/m/Miltersen:Peter_Bro.html">Peter Bro Miltersen</a>, <a href="../../indices/a-tree/s/Skyum:Sven.html">Sven Skyum</a>: Dynamic Word Problems. 470-479 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FrandsenMS93">BibTeX</a></font> <li><a name="HampapuramF93" href="../../indices/a-tree/h/Hampapuram:Haripriyan.html">Haripriyan Hampapuram</a>, <a href="../../indices/a-tree/f/Fredman:Michael_L=.html">Michael L. Fredman</a>: Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums. 480-485 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HampapuramF93">BibTeX</a></font> <li><a name="Koiran93" href="../../indices/a-tree/k/Koiran:Pascal.html">Pascal Koiran</a>: A Weak Version of the Blum, Shub & Smale model. 486-495 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Koiran93">BibTeX</a></font> <li><a name="Sharir93" href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions. 498-507 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sharir93">BibTeX</a></font> <li><a name="HershbergerS93" href="../../indices/a-tree/h/Hershberger:John.html">John Hershberger</a>, <a href="../../indices/a-tree/s/Suri:Subhash.html">Subhash Suri</a>: Efficient Computation of Euclidean Shortest Paths in the Plane. 508-517 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HershbergerS93">BibTeX</a></font> <li><a name="AronovS93" href="../../indices/a-tree/a/Aronov:Boris.html">Boris Aronov</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: The Union of Convex Polyhedra in Three Dimensions. 518-527 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AronovS93">BibTeX</a></font> <li><a name="EricksonS93" href="../../indices/a-tree/e/Erickson:Jeff.html">Jeff Erickson</a>, <a href="../../indices/a-tree/s/Seidel:Raimund.html">Raimund Seidel</a>: Better Lower Bounds on Detecting Affine and Spherical Degeneracies. 528-536 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EricksonS93">BibTeX</a></font> <li><a name="Ben-AmramG93" href="../../indices/a-tree/b/Ben=Amram:Amir_M=.html">Amir M. Ben-Amram</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>: When can we sort in o(n log n) time? 538-546 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-AmramG93">BibTeX</a></font> <li><a name="ChangG93" href="../../indices/a-tree/c/Chang:Richard.html">Richard Chang</a>, <a href="../../indices/a-tree/g/Gasarch:William_I=.html">William I. Gasarch</a>: On Bounded Queries and Approximation. 547-556 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChangG93">BibTeX</a></font> <li><a name="ShallcrossPL93" href="../../indices/a-tree/s/Shallcross:David.html">David Shallcross</a>, <a href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>, <a href="../../indices/a-tree/l/Lin=Kriz:Yu.html">Yu Lin-Kriz</a>: The NC Equivalence of Planar Integer Linear Programming and Euclidean GCD. 557-564 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ShallcrossPL93">BibTeX</a></font> <li><a name="Barvinok93" href="../../indices/a-tree/b/Barvinok:Alexander_I=.html">Alexander I. Barvinok</a>: A Polynomial Time Algorithm for Counting Integral Points in Polyhedra when the Dimension Is Fixed. 566-572 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Barvinok93">BibTeX</a></font> <li><a name="McAllisterKS93" href="../../indices/a-tree/m/McAllister:Michael.html">Michael McAllister</a>, <a href="../../indices/a-tree/k/Kirkpatrick:David_G=.html">David G. Kirkpatrick</a>, <a href="../../indices/a-tree/s/Snoeyink:Jack.html">Jack Snoeyink</a>: A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. 573-582 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/McAllisterKS93">BibTeX</a></font> <li><a name="Mitchell93" href="../../indices/a-tree/m/Mitchell:Scott_A=.html">Scott A. Mitchell</a>: Refining a Triangulation of a Planar Straight-Line Graph to Eliminate Large Angles. 583-591 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mitchell93">BibTeX</a></font> <li><a name="EvansS93" href="../../indices/a-tree/e/Evans:William_S=.html">William S. Evans</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas. 594-603 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EvansS93">BibTeX</a></font> <li><a name="HalldorssonRS93" href="../../indices/a-tree/h/Halld=oacute=rsson:Magn=uacute=s_M=.html">Magnús M. Halldórsson</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>, <a href="../../indices/a-tree/s/Subrahmanyam:K=_V=.html">K. V. Subrahmanyam</a>: Directed vs. Undirected Monotone Contact Networks for Threshold Functions. 604-613 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HalldorssonRS93">BibTeX</a></font> <li><a name="HuangI93" href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>, <a href="../../indices/a-tree/i/Ierardi:Doug.html">Doug Ierardi</a>: Counting Rational Points on Curves over Finite Fields (Extended Abstract). 616-625 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HuangI93">BibTeX</a></font> <li><a name="Reif93" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: An O(n log ^3 n) Algorithm for the Real Root Problem. 626-635 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Reif93">BibTeX</a></font> <li><a name="AwerbuchBCP93" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/b/Berger:Bonnie.html">Bonnie Berger</a>, <a href="../../indices/a-tree/c/Cowen:Lenore.html">Lenore Cowen</a>, <a href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>: Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. 638-647 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchBCP93">BibTeX</a></font> <li><a name="Cohen93" href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>: Fast algorithms for constructing t-spanners and paths with stretch t. 648-658 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cohen93">BibTeX</a></font> <li><a name="GarayKP93" href="../../indices/a-tree/g/Garay:Juan_A=.html">Juan A. Garay</a>, <a href="../../indices/a-tree/k/Kutten:Shay.html">Shay Kutten</a>, <a href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>: A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract). 659-668 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GarayKP93">BibTeX</a></font> <li><a name="FranklinGY93" href="../../indices/a-tree/f/Franklin:Matthew_K=.html">Matthew K. Franklin</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/y/Yung:Moti.html">Moti Yung</a>: Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems. 670-679 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FranklinGY93">BibTeX</a></font> <li><a name="Gillman93" href="../../indices/a-tree/g/Gillman:David.html">David Gillman</a>: A Chernoff bound for random walks on expander graphs. 680-691 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gillman93">BibTeX</a></font> <li><a name="KortsarzP93" href="../../indices/a-tree/k/Kortsarz:Guy.html">Guy Kortsarz</a>, <a href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>: On Choosing a Dense Subgraph (Extended Abstract). 692-701 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KortsarzP93">BibTeX</a></font> <li><a name="LeisersonRT93" href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>, <a href="../../indices/a-tree/t/Toledo:Sivan.html">Sivan Toledo</a>: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract). 704-713 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeisersonRT93">BibTeX</a></font> <li><a name="GoodrichTVV93" href="../../indices/a-tree/g/Goodrich:Michael_T=.html">Michael T. Goodrich</a>, <a href="../../indices/a-tree/t/Tsay:Jyh=Jong.html">Jyh-Jong Tsay</a>, <a href="../../indices/a-tree/v/Vengroff:Darren_Erik.html">Darren Erik Vengroff</a>, <a href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>: External-Memory Computational Geometry (Preliminary Version). 714-723 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoodrichTVV93">BibTeX</a></font> <li><a name="AroraBSS93" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/s/Stern:Jacques.html">Jacques Stern</a>, <a href="../../indices/a-tree/s/Sweedyk:Z=.html">Z. Sweedyk</a>: The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations. 724-733 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraBSS93">BibTeX</a></font> <li><a name="LeightonM93" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/m/Ma:Yuan.html">Yuan Ma</a>: Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract). 734-743 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonM93">BibTeX</a></font> </ul><p><div class="footer"> <a href="../../index.html">Home</a> | <a href="../indexa.html">Conferences</a> | <a href="../../journals/index.html">Journals</a> | <a href="../../series/index.html">Series</a> | <a href="../../about/faq.html">FAQ</a> — Search: <a href="http://dblp.l3s.de">Faceted</a> | <a href="http://dblp.mpi-inf.mpg.de/dblp-mirror/index.php">Complete</a> | <a href="../../indices/a-tree/index.html">Author</a></div> <small><a href="../../copyright.html">Copyright ©</a> Sat May 16 23:12:26 2009 by <a href="http://www.informatik.uni-trier.de/~ley/addr.html">Michael Ley</a> (<a href="mailto:ley@uni-trier.de">ley@uni-trier.de</a>)</small></p></body></html>
SIGMOD News
