Search results for "PCP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
150	Björn B. Brandenburg, James H. Anderson	A Comparison of the M-PCP, D-PCP, and FMLPon LITMUSRT.	OPODIS	2008	DBLP DOI BibTeX RDF
137	Irit Dinur	The PCP theorem by gap amplification.	J. ACM	2007	DBLP DOI BibTeX RDF	Gap amplification, PCP
129	Venkatesan Guruswami, Daniel Lewin 0001, Madhu Sudan 0001, Luca Trevisan	A Tight Characterization of NP with 3 Query PCPs.	FOCS	1998	DBLP DOI BibTeX RDF	Probabilistically Checkable Proofs (PCP), Proof composition, Two-prover one-round proof systems, Adaptive and non-adaptive verifiers, Completeness and soundness, Complexity Theory, Query complexity
116	Richard J. Lorentz	Creating Difficult Instances of the Post Correspondence Problem.	Computers and Games	2000	DBLP DOI BibTeX RDF	transposition table, hash table, PCP, Post Correspondence Problem, single-agent search
115	Irit Dinur, Omer Reingold	Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem.	FOCS	2004	DBLP DOI BibTeX RDF
104	Björn B. Brandenburg, James H. Anderson	An Implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP Real-Time Synchronization Protocols in LITMUSRT.	RTCSA	2008	DBLP DOI BibTeX RDF
102	Burak Kantarci, Mehmet Tahir Sandikkaya, Aysegül Gençata, Sema F. Oktug	Prudent Creditization Polling (PCP): A Novel Adaptive Polling Service for an EPON.	ONDM	2007	DBLP DOI BibTeX RDF	Optical Access Network, Passive Optical Network, IPACT, Multipoint Control Protocol, EPON
89	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	New direct-product testers and 2-query PCPs.	STOC	2009	DBLP DOI BibTeX RDF	testing, PCP, parallel repetition, direct products
84	Irit Dinur	The PCP theorem by gap amplification.	STOC	2006	DBLP DOI BibTeX RDF	gap amplification, PCP
75	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
75	Jonas Holmerin, Subhash Khot	A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.	STOC	2004	DBLP DOI BibTeX RDF	max-bisection, hardness of approximation, linear equations, PCPs
67	Jonathan Bentwich	The duality principle: irreducibility of sub-threshold psychophysical computation to neuronal brain activation.	Synth.	2006	DBLP DOI BibTeX RDF	Materialistic reductionism, Duality principle, Body-mind, Binding problem, Computation, Psychophysics, Neuroscience
67	Oded Goldreich 0001, Madhu Sudan 0001	Locally testable codes and PCPs of almost-linear length.	J. ACM	2006	DBLP DOI BibTeX RDF	error-correcting codes, derandomization, probabilistically checkable proofs, Proof verification
67	Oded Goldreich 0001, Madhu Sudan 0001	Locally Testable Codes and PCPs of Almost-Linear Length.	FOCS	2002	DBLP DOI BibTeX RDF
67	Ling Zhao	Tackling Post's Correspondence Problem.	Computers and Games	2002	DBLP DOI BibTeX RDF
64	Karsten Krogh-Jespersen, Margaret Czerw, Mira Kanzelberger, Alan S. Goldman	DFT/ECP Study of C-H Activation by (PCP)Ir and (PCP)Ir(H)2 (PCP = 3-1, 3-C6H3(CH2PR2)2). Enthalpies and Free Energies of Associative and Dissociative Pathways.	J. Chem. Inf. Comput. Sci.	2001	DBLP DOI BibTeX RDF
63	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Robust pcps of proximity, shorter pcps and applications to coding.	STOC	2004	DBLP DOI BibTeX RDF	property testing, probabilistically checkable proofs, PCP, locally decodable codes, locally testable codes
63	Venkatesan Guruswami, Sanjeev Khanna	On the Hardness of 4-Coloring a 3-Colorable Graph.	CCC	2000	DBLP DOI BibTeX RDF	Graph Coloring, Hardness of approximation, PCP
61	Subhash Khot, Rishi Saket	A 3-Query Non-Adaptive PCP with Perfect Completeness.	CCC	2006	DBLP DOI BibTeX RDF
57	Johan Håstad, Avi Wigderson	Simple Analysis of Graph Tests for Linearity and PCP.	CCC	2001	DBLP DOI BibTeX RDF	graph test, pseudorandomness, PCP, Linearity testing, iterated test
56	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev 0001	A new multilayered PCP and the hardness of hypergraph vertex cover.	STOC	2003	DBLP DOI BibTeX RDF	hypergraph vertex cover, long code, multilayered PCP, hardness of approximation
54	Xianbin Wang 0001, Yiyan Wu 0001, Hsiao-Chun Wu	A New Adaptive OFDM System with Precoded Cyclic Prefix for Cognitive Radio.	ICC	2008	DBLP DOI BibTeX RDF
54	Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky	Efficient Arguments without Short PCPs.	CCC	2007	DBLP DOI BibTeX RDF
54	Lars Engebretsen, Jonas Holmerin	Three-Query PCPs with Perfect Completeness over non-Boolean Domains.	CCC	2003	DBLP DOI BibTeX RDF
49	Venkatesan Guruswami	Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.	Algorithmica	2004	DBLP DOI BibTeX RDF	Set splitting, Hardness of approximations, PCP, Gadgets
48	Tianyan Deng, Daoyun Xu	NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k).	FAW	2008	DBLP DOI BibTeX RDF	PCP theorem, linear CNF formula, LSAT, minimal unsatisfiable(MU) formula, NP-completeness, reduction
48	Yael Tauman Kalai, Ran Raz	Interactive PCP.	ICALP (2)	2008	DBLP DOI BibTeX RDF
48	Klaus Meer	Transparent Long Proofs: A First PCP Theorem for NPR.	Found. Comput. Math.	2005	DBLP DOI BibTeX RDF	Real number complexity, Verifiers, Probabilistically checkable proofs
48	Vesa Halava, Mika Hirvensalo, Ronald de Wolf	Decidability and Undecidability of Marked PCP.	STACS	1999	DBLP DOI BibTeX RDF
44	Or Meir	Combinatorial PCPs with Efficient Verifiers.	FOCS	2009	DBLP DOI BibTeX RDF	PCPP, PCP of Proximity, super-fast, PCP
40	Mohamed Hefeeda, Hossein Ahmadi 0001	A Probabilistic Coverage Protocol for Wireless Sensor Networks.	ICNP	2007	DBLP DOI BibTeX RDF
40	César Sánchez 0001, Henny B. Sipma, Christopher D. Gill, Zohar Manna	Distributed Priority Inheritance for Real-Time and Embedded Systems.	OPODIS	2006	DBLP DOI BibTeX RDF
40	Lars Engebretsen, Jonas Holmerin	More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.	STACS	2005	DBLP DOI BibTeX RDF
40	Klaus Meer	On Some Relations Between Approximation Problems and PCPs over the Real Numbers.	CiE	2005	DBLP DOI BibTeX RDF
40	Tei-Wei Kuo, Yuan-Ting Kao, Chin-Fu Kuo	Two-Version Based Concurrency Control and Recovery in Real-Time Client/Server Databases.	IEEE Trans. Computers	2003	DBLP DOI BibTeX RDF	client/server databases, write through procedure, concurrency control, recovery, logging, Real-time database, read-only transactions
40	Jonas Holmerin	Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs.	ICALP	2002	DBLP DOI BibTeX RDF
40	Joo-Yong Kim, Sang Hyuk Son, Kern Koh	The Ceiling Adjustment Scheme for Improving the Concurrency of Real-Time Systems with Mixed Workloads.	COMPSAC	1997	DBLP DOI BibTeX RDF
40	Alexandru Mateescu, Arto Salomaa	Post Correspondence Problem: Primitivity and Interrelations with Complexity Classes.	MFCS	1993	DBLP DOI BibTeX RDF
36	Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani	The detectability lemma and quantum gap amplification.	STOC	2009	DBLP DOI BibTeX RDF	QMA, detectability lemma, gap amplification, local hamiltonians, quantum computation, PCP
36	Eli Ben-Sasson, Madhu Sudan 0001	Simple PCPs with poly-log rate and query complexity.	STOC	2005	DBLP DOI BibTeX RDF	PCPP, probabilistically checkable proofs, PCP, locally testable codes
35	Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor	The Power of Unentanglement.	CCC	2008	DBLP DOI BibTeX RDF	QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
35	Jin-yi Cai, Hong Zhu 0004	Progress in Computational Complexity Theory.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms
35		Parallel Coordinates Plot (PCP).	Encyclopedia of Database Systems	2009	DBLP DOI BibTeX RDF
35	Ran Raz	Quantum Information and the PCP Theorem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Quantum interactive proofs, Quantum advice, Quantum computation, Probabilistically checkable proofs, Quantum information, Low degree test
35	Hari Balakrishnan, Nikolaus Correll, Jakob Eriksson, Sejoon Lim, Samuel Madden 0001, Daniela Rus	PCP: the personal commute portal.	SenSys	2008	DBLP DOI BibTeX RDF	sensor network, mobility, gps, navigation, application, path planning, data visualization, transportation, traffic
35	Georgia M. Kapitsaki, Iakovos S. Venieris	PCP: privacy-aware context profile towards context-aware application development.	iiWAS	2008	DBLP DOI BibTeX RDF	privacy, context-awareness
35	Ran Raz	Quantum Information and the PCP Theorem.	FOCS	2005	DBLP DOI BibTeX RDF
35	Klaus Meer	Transparent Long Proofs: A First PCP Theorem for NPR.	ICALP	2004	DBLP DOI BibTeX RDF
35	Giuseppe Bianchi 0001, Flaminio Borgonovo, Antonio Capone, Luigi Fratta, Chiara Petrioli	PCP-DV: An End-to-End Admission Control Mechanism for IP Telephony.	IWDC	2001	DBLP DOI BibTeX RDF
35	Vesa Halava, Tero Harju, Mika Hirvensalo	Generalized PCP Is Decidable for Marked Morphisms.	FCT	1999	DBLP DOI BibTeX RDF
35	Volker Heun, Wolfgang Merkle, Ulrich Weigand	Proving the PCP-Theorem.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
35	Luca Trevisan	Positive Linear Programming, Parallel Approximation and PCP's.	ESA	1996	DBLP DOI BibTeX RDF
27	Yael Tauman Kalai, Ran Raz	Probabilistically Checkable Arguments.	CRYPTO	2009	DBLP DOI BibTeX RDF
27	Irit Dinur	PCPs with small soundness error.	SIGACT News	2008	DBLP DOI BibTeX RDF
27	Olivier Dugeon, Enzo Mingozzi, Giovanni Stea, Luca Bisti	Provisioning QoS in inter-domain traffic engineering.	Ann. des Télécommunications	2008	DBLP DOI BibTeX RDF	Path computation element, EQ-link, Traffic engineering, DiffServ, Multi protocol label switching
27	Li Yan, Sunwoo Park, Shahab Sheikh-Bahaei, Glen E. P. Ropella, C. Anthony Hunt	Predicting hepatic disposition properties of cationic drugs using a physiologically based, agent-oriented In Silico Liver.	SpringSim	2008	DBLP DOI BibTeX RDF	drug disposition, hepatic, mechanistic, physiologically-based, prediction, systems biology, agent oriented
27	Tianyan Deng, Daoyun Xu	Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems.	ICYCS	2008	DBLP DOI BibTeX RDF
27	Or Meir	Combinatorial construction of locally testable codes.	STOC	2008	DBLP DOI BibTeX RDF	pcps of proximity, probabilistically checkable proofs, locally testable codes
27	Vesa Halava, Tero Harju, Juhani Karhumäki	The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
27	Jay Walter Larson, Boyana Norris	Component Specification for Parallel Coupling Infrastructure.	ICCSA (3)	2007	DBLP DOI BibTeX RDF
27	Dana Moshkovitz, Ran Raz	Sub-constant error low degree test of almost-linear size.	STOC	2006	DBLP DOI BibTeX RDF	plane vs. point test, probabilistically checkable proofs, locally testable codes, low degree testing
27	Philippe Marchand, Purnendu Sinha	A Hardware Accelerator for Controlling Access to Multiple-Unit Resources in Safety/Time-Critical Systems.	SAMOS	2005	DBLP DOI BibTeX RDF
27	Subhash Khot, Nisheeth K. Vishnoi	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.	FOCS	2005	DBLP DOI BibTeX RDF
27	Paul Bell, Igor Potapov	On the Membership of Invertible Diagonal Matrices.	Developments in Language Theory	2005	DBLP DOI BibTeX RDF
27	Subhash Khot	Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.	FOCS	2004	DBLP DOI BibTeX RDF
27	Subhash Khot	Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.	FOCS	2002	DBLP DOI BibTeX RDF
27	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
27	Irit Dinur	Approximating SVPinfty to within Almost-Polynomial Factors Is NP-Hard.	CIAC	2000	DBLP DOI BibTeX RDF
27	Venkatesan Guruswami	Inapproximability results for set splitting and satisfiability problems with no mixed clauses.	APPROX	2000	DBLP DOI BibTeX RDF
27	Liming Cai, David W. Juedes, Iyad A. Kanj	The Inapproximability of Non NP-hard Optimization Problems.	ISAAC	1998	DBLP DOI BibTeX RDF
27	Marjo Lipponen	Post Correspondence Problem: Words Possible as Primitive Solutions.	ICALP	1995	DBLP DOI BibTeX RDF
22	Irit Dinur, Or Meir	Derandomized Parallel Repetition of Structured PCPs.	CCC	2010	DBLP DOI BibTeX RDF	Low error, Direct Product Test, Derandomized Parallel Repetition, PCP, Direct Product, de-Bruijn
22	Irit Dinur, Prahladh Harsha	Composition of Low-Error 2-Query PCPs Using Decodable PCPs.	FOCS	2009	DBLP DOI BibTeX RDF	locally decodable, low soundness error, composition, PCP
22	Ryan O'Donnell, Yi Wu 0002	Conditional hardness for satisfiable 3-CSPs.	STOC	2009	DBLP DOI BibTeX RDF	khot's, satisfiable 3-CSPs, hardness of approximation, PCP
22	Victor Chen	A Hypergraph Dictatorship Test with Perfect Completeness.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Gowers norm, Property testing, Fourier analysis, PCP
22	Jim Ras, Albert M. K. Cheng	Real-time synchronization on distributed architecture with Ada-2005.	SIGAda	2008	DBLP DOI BibTeX RDF	dpcp, dsrp, edf, ada, pcp, rms, srp
22	Tei-Wei Kuo, Ching-Hui Li	A Fixed-Priority-Driven Open Environment for Real-Time Applications.	RTSS	1999	DBLP DOI BibTeX RDF	Resource Synchronization, Real-Time Systems, EDF, PCP, Generalized Processor Sharing, Open Environment, RM, SRP, Sporadic Server
21	Boaz Barak, Oded Goldreich 0001	Universal Arguments and their Applications.	CCC	2002	DBLP DOI BibTeX RDF	Probabilistic proof systems, computationally-sound proof systems, zero-knowledge proof systems, probabilistic checkable proofs (PCP), collision-free hashing, witness indistinguishable proof systems, error-correcting codes, proofs of knowledge
21	Venkatesan Guruswami, Johan Håstad, Madhu Sudan 0001	Hardness of Approximate Hypergraph Coloring.	FOCS	2000	DBLP DOI BibTeX RDF	approximate hypergraph coloring, covering complexity, probabilistic verifier, PCP verifier, 2-colorable 4-uniform hypergraph, hardness assumption, computational complexity, computational geometry, minimisation, graph colouring, hardness, minimization problems
21	Peyman Shobeiri, Mehdi Akbarian Rastaghi, Saeid Abrishami, Behnam Shobiri	PCP-ACO: a hybrid deadline-constrained workflow scheduling algorithm for cloud environment.	J. Supercomput.	2024	DBLP DOI BibTeX RDF
21	Anand Natarajan, Chinmay Nirkhe	The status of the quantum PCP conjecture (games version).	CoRR	2024	DBLP DOI BibTeX RDF
21	Vesa Halava, Stepan Holub	Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time.	Int. J. Found. Comput. Sci.	2024	DBLP DOI BibTeX RDF
21	Vanha Tran	Meta-PCP: A concise representation of prevalent co-location patterns discovered from spatial data.	Expert Syst. Appl.	2023	DBLP DOI BibTeX RDF
21	Soni Pranshu Kumar, Nelson Leema	PCP: Profit-Driven Churn Prediction using Machine Learning Techniques in Banking Sector.	Int. J. Perform. Eng.	2023	DBLP DOI BibTeX RDF
21	Elif E. Firat, Ben Swallow, Robert S. Laramee	PCP-Ed: Parallel coordinate plots for ensemble data.	Vis. Informatics	2023	DBLP DOI BibTeX RDF
21	Jordi Weggemans, Marten Folkertsma, Chris Cade	Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture.	CoRR	2023	DBLP DOI BibTeX RDF
21	Sevag Gharibian, François Le Gall	Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
21	Xinyang Deng, Tianhan Gao, Nan Guo, Cong Zhao, Jiayu Qi	PCP: A Pseudonym Change Scheme for Location Privacy Preserving in VANETs.	Entropy	2022	DBLP DOI BibTeX RDF
21	Vikas Singh, Shachi Sharma	AHP-PCP: AHP based Probabilistic Consensus Protocol for Probabilistic Knowledge-based Blockchains.	ANTS	2022	DBLP DOI BibTeX RDF
21	Gal Arnon, Alessandro Chiesa, Eylon Yogev	A PCP Theorem for Interactive Proofs and Applications.	EUROCRYPT (2)	2022	DBLP DOI BibTeX RDF
21	Sevag Gharibian, François Le Gall	Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture.	STOC	2022	DBLP DOI BibTeX RDF
21	Cristina Cornelio, Judy Goldsmith, Umberto Grandi, Nicholas Mattei, Francesca Rossi 0001, Kristen Brent Venable	Reasoning with PCP-Nets.	J. Artif. Intell. Res.	2021	DBLP DOI BibTeX RDF
21	Sevag Gharibian, François Le Gall	Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.	CoRR	2021	DBLP BibTeX RDF
21	Hengzhao Ma, Jianzhong Li 0001	The PCP-like Theorem for Sub-linear Time Inapproximability.	CoRR	2021	DBLP BibTeX RDF
21	George Kadianakis, Theodoros Polyzos, Mike Perry, Kostas Chatzikokolakis 0001	PCP: Preemptive Circuit Padding against Tor circuit fingerprinting.	CoRR	2021	DBLP BibTeX RDF
21	Gal Arnon, Alessandro Chiesa, Eylon Yogev	A PCP Theorem for Interactive Proofs.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
21	Klaus Meer	A PCP of Proximity for Real Algebraic Polynomials.	CSR	2021	DBLP DOI BibTeX RDF
21	Abhishek Patyal, Po-Cheng Pan, K. A. Asha, Hung-Ming Chen, Wei-Zen Chen	Exploring Multiple Analog Placements With Partial-Monotonic Current Paths and Symmetry Constraints Using PCP-SP.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	2020	DBLP DOI BibTeX RDF
21		PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability.	CoRR	2020	DBLP BibTeX RDF
21	Nagaganesh Jaladanki, Wilson Wu	Distributed Verifiers in PCP.	CoRR	2020	DBLP BibTeX RDF