Search results for "PCP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
21	Oded Goldreich 0001, Shmuel Safra	A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.	SIAM J. Comput.	2000	DBLP DOI BibTeX RDF
21	Alex Samorodnitsky, Luca Trevisan	A PCP characterization of NP with optimal amortized query complexity.	STOC	2000	DBLP DOI BibTeX RDF
21	Luca Trevisan	A Survey of Optimal PCP Characterizations of NP.	CCC	2000	DBLP DOI BibTeX RDF
21	Flaminio Borgonovo, Antonio Capone, Luigi Fratta, Mario Marchese, Chiara Petrioli	PCP: a bandwidth guaranteed transport service for IP networks.	ICC	1999	DBLP DOI BibTeX RDF
21	Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra	PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.	STOC	1999	DBLP DOI BibTeX RDF
21	Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra	PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
21	Georgios Sfikas, Costas Apostolas, Rahim Tafazolli	The U.K. LINK-PCP approach to the wireless ATM system.	IEEE Commun. Mag.	1997	DBLP DOI BibTeX RDF
21	Oded Goldreich 0001, Shmuel Safra	A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.	RANDOM	1997	DBLP DOI BibTeX RDF
21	Ran Raz, Shmuel Safra	A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.	STOC	1997	DBLP DOI BibTeX RDF
21	Amnon Ta-Shma	A Note on PCP vs. MIP.	Inf. Process. Lett.	1996	DBLP DOI BibTeX RDF
21	Oded Goldreich 0001, Shmuel Safra	A Combinatorial Consistency Lemma with application to the PCP Theorem	Electron. Colloquium Comput. Complex.	1996	DBLP BibTeX RDF
21	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCP and Non-Approximability - Towards Tight Results	Electron. Colloquium Comput. Complex.	1995	DBLP BibTeX RDF
21	Marjo Lipponen, Gheorghe Paun	Strongly Prime PCP Words.	Discret. Appl. Math.	1995	DBLP DOI BibTeX RDF
21	Marjo Lipponen	Primitive Words and Languages Associated to PCP.	Bull. EATCS	1994	DBLP BibTeX RDF
21	Alexandru Mateescu, Arto Salomaa	PCP-Prime Words and Primality Types.	RAIRO Theor. Informatics Appl.	1993	DBLP DOI BibTeX RDF
21	Pauline M. Berry	The PCP: A predictive model for satisfying conflicting objectives in scheduling problems.	Artif. Intell. Eng.	1992	DBLP DOI BibTeX RDF
21	Eugene D. Brooks III, Brent C. Gorda, Karen H. Warren	The PCP/PFP Programming Models on the BBN TC2000.	ACPC	1991	DBLP DOI BibTeX RDF
13	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	ACM Trans. Algorithms	2009	DBLP DOI BibTeX RDF	pebble placement, graphs, Motion planning, Euclidean plane
13	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
13	Luca Trevisan	Guest column: additive combinatorics and theoretical computer science.	SIGACT News	2009	DBLP DOI BibTeX RDF
13	Ryan O'Donnell, Yi Wu 0002	3-bit dictator testing: 1 vs. 5/8.	SODA	2009	DBLP DOI BibTeX RDF
13	Erwan Jahier, Nicolas Halbwachs, Pascal Raymond	Synchronous Modeling and Validation of Priority Inheritance Schedulers.	FASE	2009	DBLP DOI BibTeX RDF	Simulation, Scheduling, Embedded systems, Formal Verification, Architecture Description Languages, Synchronous Languages
13	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
13	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 94A60, 68P25
13	Haiyong Xie 0001, Yang Richard Yang, Avi Silberschatz	Towards an ISP-Compliant, Peer-Friendly Design for Peer-to-Peer Networks.	Networking	2008	DBLP DOI BibTeX RDF
13	Paul Valiant	Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency.	TCC	2008	DBLP DOI BibTeX RDF
13	Angsheng Li, Linqing Tang	Derandomizing Graph Tests for Homomorphism.	TAMC	2008	DBLP DOI BibTeX RDF
13	Klaus Meer	Some Relations between Approximation Problems and PCPs over the Real Numbers.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
13	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	SODA	2007	DBLP BibTeX RDF
13	San-Min Wang, Zhi-jun Lu	How to Construct Formal Systems for Fuzzy Logics.	IFSA (2)	2007	DBLP DOI BibTeX RDF	Weakly implicative logic, weakly implicative fuzzy logic, the proof by cases property, substructural fuzzy logics
13	Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis	Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.	FOCS	2007	DBLP DOI BibTeX RDF
13	Marko Bertogna, Nathan Fisher, Sanjoy K. Baruah	Static-Priority Scheduling and Resource Hold Times.	IPDPS	2007	DBLP DOI BibTeX RDF
13	Frank Singhoff	MP1: real time scheduling theory and its use with ada.	SIGAda	2007	DBLP DOI BibTeX RDF
13	Xiaofeng Lin, Zhigang Zhang, Derong Liu 0001	Temperature Control in Precalcinator with Dual Heuristic Dynamic Programming.	IJCNN	2007	DBLP DOI BibTeX RDF
13	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
13	Pierre Chambart, Philippe Schnoebelen	Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems.	FSTTCS	2007	DBLP DOI BibTeX RDF	Lossy channel systems, Higman’s Lemma, Post correspondence problem
13	Marcel Dischinger, Andreas Haeberlen, P. Krishna Gummadi, Stefan Saroiu	Characterizing residential broadband networks.	Internet Measurement Conference	2007	DBLP DOI BibTeX RDF	broadband access networks, cable, network measurement, dsl
13	Ronald Sidharta, James H. Oliver, Adrian Sannier	Augmented Reality Tangible Interface for Distributed Design Review.	CGIV	2006	DBLP DOI BibTeX RDF	augmented reality, virtual environment, CAD, collaborative design, information architecture
13	Jaikumar Radhakrishnan	Gap Amplification in PCPs Using Lazy Random Walks.	ICALP (1)	2006	DBLP DOI BibTeX RDF
13	Alex Samorodnitsky, Luca Trevisan	Gowers uniformity, influence of variables, and PCPs.	STOC	2006	DBLP DOI BibTeX RDF	influence of variables, probabilistically checkable proofs, linearity test
13	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification Via Space-Efficient Direct Products.	LATIN	2006	DBLP DOI BibTeX RDF	error-correcting codes, expanders, Direct products, hardness amplification
13	Allan Borodin	Further Reflections on a Theory for Basic Algorithms.	AAIM	2006	DBLP DOI BibTeX RDF
13	László Babai, Amir Shpilka, Daniel Stefankovic	Locally testable cyclic codes.	IEEE Trans. Inf. Theory	2005	DBLP DOI BibTeX RDF
13	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
13	Shipeng Yu, Kai Yu 0001, Volker Tresp, Hans-Peter Kriegel	A Probabilistic Clustering-Projection Model for Discrete Data.	PKDD	2005	DBLP DOI BibTeX RDF
13	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
13	Giordano Cabral 0001, François Pachet, Jean-Pierre Briot	Recognizing Chords with EDS: Part One.	CMMR	2005	DBLP DOI BibTeX RDF
13	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Subhash Khot	Hardness of Max 3SAT with No Mixed Clauses.	CCC	2005	DBLP DOI BibTeX RDF
13	Igor Potapov	From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata.	Developments in Language Theory	2004	DBLP DOI BibTeX RDF
13	Christos Kloukinas	Data-Mining Synthesised Schedulers for Hard Real-Time Systems.	ASE	2004	DBLP DOI BibTeX RDF	scheduler synthesis, data-mining, Software engineering, schedulability analysis, hard real-time systems, decision-tree induction
13	Sanjeev Arora, Madhu Sudan 0001	Improved Low-Degree Testing and its Applications.	Comb.	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q10, 68Q17
13	Erich L. Kaltofen	Polynomial factorization: a success story.	ISSAC	2003	DBLP DOI BibTeX RDF	black box polynomial, randomized algorithm, polynomial factorization, lattice basis reduction, symbolic/numeric hybrid method, straight line program
13	Saowanee Saewong, Ragunathan Rajkumar, John P. Lehoczky, Mark H. Klein	Analysis of Hierar hical Fixed-Priority Scheduling.	ECRTS	2002	DBLP DOI BibTeX RDF
13	Kasturi R. Varadarajan, Srinivasan Venkatesh 0001, Jiawei Zhang	On Approximating the Radii of Point Sets in High Dimensions.	FOCS	2002	DBLP DOI BibTeX RDF
13	Sita Ramakrishnan	DoIT: dynamic curriculum organisation by innovation through technology.	ITiCSE	2002	DBLP DOI BibTeX RDF
13	Subhash Khot	Hardness results for approximate hypergraph coloring.	STOC	2002	DBLP DOI BibTeX RDF
13	Prahladh Harsha, Madhu Sudan 0001	Small PCPs with Low Query Complexity.	STACS	2001	DBLP DOI BibTeX RDF
13	Vladimir Geroimenko, Larissa Geroimenko	Visualizing Human Consciousness Content Using Java3D/X3D and Psychological Techniques.	IV	2000	DBLP DOI BibTeX RDF	Twin VR technology, Personal Construct Psychology, Virtual environments, X3D, 3D visualization, Java3D, Repertory Grid Technique
13	Johan Håstad	Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?	ICALP	2000	DBLP DOI BibTeX RDF
13	Vikraman Arvind, K. V. Subrahmanyam 0001, N. V. Vinodchandran	The Query Complexity of Program Checking by Constant-Depth Circuits.	ISAAC	1999	DBLP DOI BibTeX RDF
13	Andrés Terrasa, Ana García-Fornes	Real-Time Synchronization Between Hard and Soft Tasks in RT-Linux.	RTCSA	1999	DBLP DOI BibTeX RDF	real-time synchronization, real-time operating systems, priority inheritance
13	Jens Knoop	Parallel Constant Propagation.	Euro-Par	1998	DBLP DOI BibTeX RDF
13	Martin Mundhenk, Anna Slobodová	Optimal Non-approximability of MAXCLIQUE.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
13	Stefan Hougardy	Proof Checking and Non-approximability.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
13	Tero Harju, Juhani Karhumäki, Daniel Krob	Remarks on Generalized Post Correspondence Problem.	STACS	1996	DBLP DOI BibTeX RDF
13	Manuel Blum 0001, Bruno Codenotti, Peter Gemmell, Troy Shahoumian	Self-Correcting for Function Fields Transcendental Degree.	ICALP	1995	DBLP DOI BibTeX RDF
13	Joe Kilian	Improved Efficient Arguments (Preliminary Version).	CRYPTO	1995	DBLP DOI BibTeX RDF
13	Gérard Berry	Stable Models of Typed lambda-Calculi.	ICALP	1978	DBLP DOI BibTeX RDF