TY - CHAP
AB - Rezension: Zbl. Math. 1100.03006 (I. Grattan-Guinness)
AU - Peckhaus, Volker
ED - Beaney, Michael
ED - Reck, Erich H.
ID - 17563
T2 - Gottlob Frege. Critical Assessments of Leading Philosophers, Bd. 1: Frege’s Philosophy in Context
TI - Calculus Ratiocinator vs. Characteristica Universalis? The Two Traditions in Logic, Revisted (Wiederabdruck)
ER -
TY - JOUR
AU - Ziegler, Martin
ID - 18282
IS - 11
JF - International Journal of Theoretical Physics
SN - 0020-7748
TI - Computational Power of Infinite Quantum Parallelism
VL - 44
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18509
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 1056.01012]
TI - Bolzano, Bernard, Miscellanea mathematica 19, hg. v. Bob van Rootselar/Anna van der Lugt, Frommann-Holzboog: Stuttgart-Bad Cannstatt 2005 (Bernard Bolzano-Gesamtausgabe; II.B.11.1)
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18504
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 1049.01012]
TI - Lewis, Albert C., “The Unity of Logic, Pedagogy and Foundations in Grassmann's Mathematical Work”, History and Philosophy of Logic 25 (2004), 15–36
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18516
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 1060.01003]
TI - Vandoulakis, Ioannis, “Was Euclid’s Approach to Arithmetic Axiomatic?”, Oriens Occidens 2 (1998), 141–181
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18511
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 1056.03001]
TI - Bochenski, Joseph M., Formale Logik, 5. unveränderte Aufl., Karl Alber: Freiburg/München 2002
ER -
TY - JOUR
AB - Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs . We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension , then the property has an efficient tester.
We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size.
Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.
AU - Czumaj, Artur
AU - Sohler, Christian
ID - 18763
IS - 3
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Abstract Combinatorial Programs and Efficient Property Testers
VL - 34
ER -
TY - CONF
AU - Bădoiu, Mihai
AU - Czumaj, Artur
AU - Indyk, Piotr
AU - Sohler, Christian
ID - 18768
SN - 0302-9743
T2 - Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)
TI - Facility Location in Sublinear Time
ER -
TY - CONF
AB - A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space {1,..., ∆} d [26]. We develop streaming (1 + ɛ)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points (a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly(ɛ −1, log m, log ∆) space and update time per insert/delete operation for constant k and dimension d. Having a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log(1/ɛ)/ɛ) d−1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1/ɛ) O(1))) time. For MaxST and average distance we require poly(log n, ɛ −1) time and for MaxWM we require O(n 3) time to do this.
AU - Sohler, Christian
AU - Frahling, Gereon
ID - 18787
T2 - Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)
TI - Coresets in Dynamic Geometric Data Streams
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18807
T2 - Mathematical Reviews [MR 2005d:00008; MathSciNet 2081800]
TI - Murawski, Roman, “Leibniz’s and Kant’s Philosophical Ideas and the Development of Hilbert’s Programme”, Logique et Analyse (N.S.) 45 (2002), 421–437
ER -